function - Why do these folds stop at the head/tail? -


i'm reading learnyouahaskell.com , investigating folds. in book there these examples:

maximum' :: (ord a) => [a] ->   maximum' = foldr1 (\x acc -> if x > acc x else acc)    reverse' :: [a] -> [a]   reverse' = foldl (\acc x -> x : acc) []    product' :: (num a) => [a] ->   product' = foldr1 (*)    filter' :: (a -> bool) -> [a] -> [a]   filter' p = foldr (\x acc -> if p x x : acc else acc) []    head' :: [a] ->   head' = foldr1 (\x _ -> x)    last' :: [a] ->   last' = foldl1 (\_ x -> x)  

i understand of them except head' , tail'.

it understanding binary function should applied accumulator , each element in list in turn, , go through list. why stop head (or tail, respectively)?

i understand _ (underscore) means "whatever" or "i don't care" how stop going through list?

let's have @ definition of foldr1 first:

foldr1 :: (a -> -> a) -> [a]       -> foldr1    f                [x]       =  x foldr1    f                (x : xs)  =  f x (foldr1 f xs) 

then, consider call of function head',

head' :: [a] ->   head' =  foldr1 (\x _ -> x) 

to list, say, [2, 3, 5]:

head' [2, 3, 5] 

now, filling in right hand-side of head' gives

foldr1 (\x _ -> x) [2, 3, 5] 

recall [2, 3, 5] syntactic sugar (2 : 3 : 5 : []). so, second case of definition of foldr1 applies , yield

(\x _ -> x) 2 (foldr1 (\x _ -> x) (3 : 5 : []) 

now, reducing applications results in 2 getting bound x , foldr1 (\x _ -> x) (3 : 5 : []) getting bound ignored parameter _. left right-hand side of lambda-abstraction x replaced 2:

2 

note lazy evaluation makes ignored argument foldr1 (\x _ -> x) (3 : 5 : []) left unevaluated , so—and answers question—the recursion stops before have processed remainder of list.


Comments

Popular posts from this blog

blackberry 10 - how to add multiple markers on the google map just by url? -

php - guestbook returning database data to flash -

delphi - Dynamic file type icon -