2

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?

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Adrian Kozień
  • 41
  • 4
  • 1
    [`foldl` can be defined in terms of `foldr`](https://stackoverflow.com/questions/53057923/defining-foldl-in-terms-of-foldr), so yes. – chepner May 02 '19 at 13:29
  • [`foldr` can also be written in terms of `foldl`](https://wiki.haskell.org/Foldl_as_foldr), but only for finite lists. – chepner May 02 '19 at 13:30

2 Answers2

3

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.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
HTNW
  • 27,182
  • 1
  • 32
  • 60
0

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

Robin Zigmond
  • 17,805
  • 2
  • 23
  • 34
  • 2
    Surely [`foldl1`](https://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.List.html#foldl1) and [`foldr1`](https://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.List.html#foldr1) are cheating? – HTNW May 02 '19 at 16:43
  • In a sense, yes - but since they can be rewritten in terms of "plain" `foldl` and `foldr` (except for empty lists, but then `head` and `tail` crash too) I don't see how you can say this isn't a solution. It's not particularly clear what motivates the OP's question, other than simple curiosity, so I can't say whether this is acceptable or not. But it seems ok to me. – Robin Zigmond May 02 '19 at 16:47