CODEWITHSUNDEEP
haskellfold
Adrian Kozień
Adrian Kozień

Reputation: 41

Finding head of a list using foldl and the last element using foldr

It is known that we can find head of a list using foldr like this:

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

but, is there any way to get the same result using foldl?

Similarly, we can find the last element of list using foldl like this:

last'' :: [a] -> a
last'' = foldl (\_ x -> x) undefined

Is there any way to get the same result using foldr?

Upvotes: 2

Views: 2116

Answers (2)

HTNW
HTNW

Reputation: 29193

head cannot be written with foldl, because foldl goes into an infinite loop on infinite lists, while head doesn't. Otherwise, sure:

head' :: [a] -> a
head' = fromJust . foldl (\y x -> y <|> Just x) Nothing

Drop the fromJust for a safe version.

last can definitely be written as a foldr, in about the same way:

last' :: [a] -> a
last' = fromJust . foldr (\x y -> y <|> Just x) Nothing

For head, we start with Nothing. The first element (the wanted one) is wrapped into Just and used to "override" the Nothing with (<|>). The following elements are ignored. For last, it's about the same, but flipped.

Upvotes: 3

Robin Zigmond
Robin Zigmond

Reputation: 18249

The first thing that springs to mind is to use foldl1 instead of foldl, then:

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

and since foldl1 is defined in terms of foldl if the list is non-empty (and crashes if the list is empty - but so does head):

foldl1 f (x:xs) = foldl f x xs

we can say

head'' (x:xs) = foldl (\x _ -> x) x xs

The same of course for last, using foldr1

Upvotes: 0

Related Questions