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
Post a Comment