7

I have a graph of Function f(n) where it returns 

5  if n = 0 
2  if n = 1 
-4 if n = 2 
1  if n = 3 
9  if n = 4 
8  if n = 5 
9  if n = 6 
0  otherwise

and I wanted to write a function that will represent a graph with one List with pairs:

type Nat0 = Int 
type Z = Int
type List = [Z] 
type Graph = [(Nat0,Z)] 

list_to_graph :: List -> Graph
list_to_graph x = list_to_graph' ([0..(length x)-1 ]) (x)

list_to_graph' :: [Int] -> List -> Graph
list_to_graph' (x:xs) (y:ys) = [(x, y)] ++ list_to_graph' (xs) (ys)
list_to_graph' [] [] = []

And thats what I did here. Passing a list [5,2,-4,1,9,8,9] returns 

*Main> list_to_graph [5,2,-4,1,9,8,9]
[(0,5),(1,2),(2,-4),(3,1),(4,9),(5,8),(6,9)]

and here is the function that does oposite:

graph_to_list :: Graph -> List
graph_to_list (x:xs) = [snd (x)] ++ graph_to_list(xs)
graph_to_list []= []

where passing the graph [(0,5),(1,2),(2,-4),(3,1),(4,9),(5,8),(6,9)]

*Main> graph_to_list [(0,5),(1,2),(2,-4),(3,1),(4,9),(5,8),(6,9)]
[5,2,-4,1,9,8,9]

Question:

What I dont understand is how to write something like this: 

type Function = (Nat0 -> Z) 

function_to_list :: Function -> List

or 

list_to_function :: List -> Function

or the same for graph 

function_to_graph :: Function -> Graph
graph_to_function :: Graph -> Function

I have read Higher order functions on this link but I cant seem to grasp how this actually works.

I suppose in function_to_list I would have to pass a function that has this notation (Nat0 -> Z)(which is actually Int -> Int ) and it should return a List with [Z] (which is [Int] ). But how do I do that? That is like passing same function to itself?

Even more confusing is the list_to_function what should here be the result?

If somebody can explain me higher order Functions on some of my examples I would really be thankful!

EDIT:

To be more clear here is what I want to achieve: 

(list_to_graph . graph_to_list) = λ x. x
(graph_to_list . list_to_graph) = λ x. x

As I showed above if I pass a list to list_to_graph it return a graph and graph_to_list does oposite

(list_to_function . function_to_list) = λ x. x
(function_to_list . list_to_function) = λ x. x

its the same that I want to do with the other two functions. If I apply function_to_list to list_to_function as function_to_list returns a List and list_to_function accepts a List it should return a function that will take a elements out of the list and apply it to Function which will return a Z.

What I figured out by now: 

function_to_list :: Function-> List
function_to_list f = [f(x) | x <- [0..6]]

function :: Function
function n
         | n == 0 = 5
         | n == 1 = 2 
         | n == 2 = (-4)
         | n == 3 = 1
         | n == 4 = 9
         | n == 5 = 8
         | n == 6 = 9
         | otherwise = 0

As the answer bellow suggested.

*Main> function_to_list function 
[5,2,-4,1,9,8,9]

What I want to do is to make this function :: Function in my list_to_function

Improve this question
1
  • You just looking for the inverse function of function. but it is impossible, since function 4 = function 6 = 9, not one to one or injective function. Commented Dec 2, 2018 at 8:16

2 Answers 2

Reset to default
3 
list_to_graph' :: [Int] -> List -> Graph
list_to_graph' (x:xs) (y:ys) = [(x, y)] ++ list_to_graph' (xs) (ys)
list_to_graph' [] [] = []

This function exists and is called zip.

Note: zip also works for lists of different length, ignoring the the extra bit of the longer list, whereas yours fails if both are not of the same length

graph_to_list :: Graph -> List
graph_to_list (x:xs) = [snd (x)] ++ graph_to_list(xs)
graph_to_list []= []

You could write this function as,

graph_to_list = map snd

or

graph_to_list xs = [snd x | x <- xs]

or

graph_to_list xs = [a | (a,b) <- xs]

Regarding this,

What I dont understand is how to write something like this:

type Function = (Nat0 -> Z) 

function_to_list :: Function -> List

If I understand you correctly you would like to be able to build the "image of f", that is a list all values f x for all x in the domain of f. Something that in theory could look like,

[f(x) | x <- DOMAIN f]

However in general there is no way to know the domain of a given function (much less a way to traverse it). Same goes for the translation of a function into a graph. To implement such "transformations" you have to provide as argument both your function f :: A -> B and a list xs :: A with the points of its domain which you want to consider.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Thanks for the answer, I edited the question to explain better what I actually mean
I understood what you want, but in your edit function_to_list assumes the the list of points [0..6]. Of course that works for that specific function but not for others. Also to revert and obtain the original function you need to assume you know that all other points return 0. It'd be list_to_function xs = \n -> if (n >=0) && (n<=6) then xs!!n else 0
Note that snd x : graph_to_list xs is preferable to [snd x] ++ graph_to_list x, as it doesn't create an unnecessary singleton list before merging it into the recursive result.
2

So you are trying to get 

list_to_function :: List -> Function

correct? Let's do Graph instead, it will get closer to the essence. Let's start writing it.

graph_to_function gph = _ -- something of type Function

So we want to construct something of type Function, that is, Nat0 -> Z. The most boring way to do that is with a lambda:

graph_to_function gph = \n -> _ -- something of type Z

Great, now we have a Graph called gph and a Nat0 called n, and we want to make a Z. Here we can just search the list for n. There are a few ways to do this, here's one:

graph_to_function gph = \n -> head ([ y | (x,y) <- gph, x == n ] ++ [0])

I put ++ [0] on the end just in case the list comprehension ends up empty, that is, we didn't find n in the domain of the graph. Done!

Fun fact, functions in Haskell are curried by default, so

f x y z = ...
f = \x -> \y -> \z -> ...

are equivalent. That is, graph_to_function is really just the same thing as a two-argument function. So we can move the n over to the left side of the definition:

graph_to_function :: Graph -> Function
graph_to_function gph n = head ([ y | (x,y) <- gph, x == n ] ++ [0])

It's looks a bit weird to have only one argument in the signature are two arguments in the equation, but it is something that you see in the wild, once you get used to it.

Hope this helps!

Improve this answer

3 Comments

Thank you that is clear to me now. The thing that is not clear to me is how to write function_to_list or function_to_graph as answer above mentioned that we cant do it without adding the argument.
@cheshire, does function_to_list f = map f [0..] do what you want?
a little bit late, but that with [0..] actually worked! Thanks

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.