Нахождение заголовка списка, используя foldl, и последний элемент, используя foldr.

Question

Известно, что мы можем найти head списка, используя foldr, например:

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

но есть ли способ получить тот же результат, используя foldl?

Аналогичным образом, мы можем найти последний элемент списка, используя foldl, например:

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

Есть ли способ получить тот же результат, используя foldr?

Answer 1

head нельзя записать с помощью foldl, поскольку foldl входит в бесконечный цикл в бесконечных списках, а head - нет.В противном случае, обязательно:

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

Удалите fromJust для безопасной версии.

last определенно можно записать как foldr, примерно так же:

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

Для head мы начинаем с Nothing.Первый элемент (требуемый) обернут в Just и используется для «переопределения» Nothing с помощью (<|>).Следующие элементы игнорируются.Для last примерно то же самое, но перевернуто.

Answer 2

Первое, что приходит на ум, - это использовать foldl1 вместо foldl, затем:

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

и, поскольку foldl1 определяется в терминах foldl, если списокнепусто (и вылетает, если список пуст - но так же head):

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

мы можем сказать

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

То же самое, конечно, для last,используя foldr1