CODEWITHSUNDEEP
listhaskellfoldfunction-definition
JavaDumbell
JavaDumbell

Reputation: 235

Understanding function which implements foldr and foldl

There is some case where I don't understand how foldr and foldl are used in function.

Here is a couple of example, I then explain why I don't understand them:

-- Two implementation of filter and map
map' f = foldr (\x acc -> (f x):acc) [] 
map'' f xs = foldl (\acc x -> acc ++ [(f x)]) [] xs 

filter' f xs = foldr(\x acc -> if(f x) then x:acc else acc) [] xs 
filter'' f  = foldl(\acc x -> if(f x) then acc++[x] else acc) []

Why does map'' makes the use of xs but non map'? Shouldn't map' need a list for the list comprehension formula as well?

Same case for filter' vs filter''.

Here is an implementation which insert elements in a sorted sequence:

insert e [] = [e]
insert e (x:xs)
     | e > x = x: insert e xs
     | otherwise = e:x:xs
sortInsertion xs = foldr insert [] xs
sortInsertion'' xs = foldl (flip insert) [] xs

Why are the argument for insert flipped in sortInsertion ([] xs) (empty list and list) compare to the definition of insert(e []) (element and empty list)

Upvotes: 2

Views: 132

Answers (2)

Jon Purdy
Jon Purdy

Reputation: 55069

Why does map'' makes the use of xs but non map'? Shouldn't map' need a list for the list comprehension formula as well? Same case for filter' vs filter''.

This is called “eta-reduction” and it’s a common way of omitting redundant parameter names (“point-free style”). Essentially whenever you have a function whose body is just an application of a function to its argument, you can reduce away the argument:

add :: Int -> Int -> Int
add x y = x + y

-- “To add x and y, call (+) on x and y.”
add :: (Int) -> (Int) -> (Int)
add x y = ((+) x) y

-- “To add x, call (+) on x.”
add :: (Int) -> (Int -> Int)
add x = (+) x

-- “To add, call (+).”
add :: (Int -> Int -> Int)
add = (+)

More precisely, if you have f x = g x where x does not appear in g, then you can write f = g.

A common mistake is then wondering why f x = g . h x can’t be written as f = g . h. It doesn’t fit the pattern because the (.) operator is the top-level expression in the body of f: it’s actually f x = (.) g (h x). You can write this as f x = (((.) g) . h) x and then reduce it to f = (.) g . h or f = fmap g . h using the Functor instance for ->, but this isn’t considered very readable.

Why are the argument for insert flipped in sortInsertion

The functional parameters of foldr and foldl have different argument order:

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

Or, with more verbose type variable names:

foldr
  :: (Foldable container)
  => (element -> accumulator -> accumulator)
  -> accumulator -> container element -> accumulator

foldl
  :: (Foldable container)
  => (accumulator -> element -> accumulator)
  -> accumulator -> container element -> accumulator

This is just a mnemonic for the direction that the fold associates:

foldr f z [a, b, c, d]
==
f a (f b (f c (f d z)))  -- accumulator on the right (second argument)

foldl f z [a, b, c, d]
==
f (f (f (f z a) b) c) d  -- accumulator on the left (first argument)

Upvotes: 7

Enlico
Enlico

Reputation: 28510

That is partial function application.

map' f = foldr (\x acc -> (f x):acc) []

is just the same as

map' f xs = foldr (\x acc -> (f x):acc) [] xs

if you omit xs on both sides.

However, beside this explanation, I think you need a beginner book for Haskell. Consider LYAH.

Upvotes: 5

Related Questions