views:

225

answers:

3

I my last question about haskell, the answer provided gave me another doubt... Instead of using the somewhat complex function in my other question, here's a simpler example:

sumAll :: [(Int,Int)] -> Int
sumAll xs = foldr (+) 0 (map f xs)
  where f (x,y) = x+y

Calling sumAll [(1,1),(2,2),(3,3)] the output will be 12.

What I don't understand is where the (x,y) values are coming from. Well, I know they come from the xs variable but I don't understand how. I mean, doing the code above directly without the where keyword, it would be something like this:

sumAll xs = foldr (+) 0 (map (\(x,y) -> x+y) xs)

And I can't understand, in the top code, how does the f variable and (x,y) variables represent the (\(x,y) -> x+y) lambda expression.

+5  A: 

In Haskell, functions are first class datatypes.

This means you can pass functions around like other types of data such as integers and strings.

In your code above you declare 'f' to be a function, which takes in one argumenta (a tuple of two values (x,y)) and returns the result of (x + y).

foldr is another function which takes in 3 arguments, a binary function (in this case +) a starting value (0) and an array of values to iterator over.

In short 'where f (x,y) = x + y' is just scoped shorthand for

sumAll :: [(Int,Int)] -> Int
sumAll xs = foldr (+) 0 (map myFunctionF xs)

myFunctionF :: (Int,Int) -> Int
myFunctionF (x,y) = x + y

Edit: If your unsure about how foldr works, check out Haskell Reference Zvon Below is an example implementation of foldl / map.

foldl :: (a -> b -> b) -> b -> [a] -> b
foldl _ x [] = x
foldl fx (y:ys) = foldl f (f y x) ys

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : (map f xs)
Akusete
+6  A: 

Hopefully this will help. The key is that f is applied to the elements of the list, which are pairs.

sumAll [(1,1),(2,2),(3,3)] 
      -- definition of sumAll
    = foldr (+) 0 (map f [(1,1),(2,2),(3,3)])
      -- application of map
    = foldr (+) 0 (f (1,1) : map f [(2,2),(3,3)])
      -- application of foldr
    = 0 + foldr (+) (f (1,1)) (map f [(2,2),(3,3)])
      -- application of map
    = 0 + foldr (+) (f (1,1)) (f (2,2) : map f [(3,3)])
      -- application of foldr
    = 0 + (f (1,1) + foldr (+) (f (2,2)) (map f [(3,3)]))
      -- application of f
    = 0 + (2 + foldr (+) (f (2,2)) (map f [(3,3)]))
      -- application of map
    = 0 + (2 + foldr (+) (f (2,2)) (f (3,3) : map f []))
      -- application of foldr
    = 0 + (2 + (f (2,2) + foldr (+) (f (3,3)) (map f [])))
      -- application of f
    = 0 + (2 + (4 + foldr (+) (f (3,3)) (map f [])))
      -- application of map
    = 0 + (2 + (4 + foldr (+) (f (3,3)) []))
      -- application of foldr
    = 0 + (2 + (4 + f (3,3)))
      -- application of f
    = 0 + (2 + (4 + 6))
    = 0 + (2 + 10)
    = 0 + 12
    = 12
Chris Conway
+2  A: 

Not an answer, but I thought I should point out that your function f:

f (x, y) = x + y

can be expressed as

f = uncurry (+)
Magnus