Использование сворачивания Haskell

Question

Я изучаю Haskell, и я боролся с этой проблемой:

Напишите func :: (a -> Bool) -> [a] -> [a] (принимайте элементы списка, пока предикат не станет ложным), используя foldr

Это то, что я до сих пор:

func :: (a -> Bool) -> [a] -> [a]
func f li = foldr f True li

и получил следующие ошибки:

Couldn't match expected type ‘[a]’ with actual type ‘Bool’

и

Couldn't match type ‘Bool’ with ‘Bool -> Bool’
Expected type: a -> Bool -> Bool
Actual type: a -> Bool

I 'Я немного сбит с толку, так как я узнал foldr, передав функцию с двумя аргументами и получив одно значение.Например, я использовал функцию, вызывая

foldr (\x -> \y -> x*y*5) 1 [1,2,3,4,5] 

, чтобы получить одно значение, но не уверен, как она работает при передаче функции с одним аргументом в foldr и получении списка в ответ.Большое спасибо.

Answer 1

Давайте сначала сделаем более простой случай и напишем функцию, которая использует foldr, чтобы ничего не делать (чтобы разбить список и создать тот же список).Давайте посмотрим на сигнатуру типа foldr:

foldr :: (a -> b -> b) -> b -> [a] -> [b]

И мы хотим написать выражение вида

foldr ?1 ?2 :: [a] -> [a]

Теперь это говорит нам об этом (в сигнатуре foldr) мы можем заменить b на [a].

То, что мы еще не разработали, ?2, это то, чем мы заменяем конец списка, и оно имеет тип b = [a],На самом деле у нас нет ничего типа a, поэтому давайте попробуем самую глупую вещь, которую мы можем:

foldr ?1 []

А теперь следующая недостающая вещь: у нас есть ?1 :: a -> [a] -> [a].Давайте напишем функцию для этого.Теперь есть две разумные вещи, которые мы можем сделать со списком вещей и другой вещью и ничего больше:

1. Добавить его в начало
2. Добавить его в конец

Я думаю, что 1 более разумно, поэтому давайте попробуем это:

myFunc = foldr (\x xs -> x : xs) []

И теперь мы можем попробовать это:

> myFunc [1,2,3,4]
[1,2,3,4]

---

Так что же такое интуиция?для foldr здесь?Один из способов понять, что переданная функция помещается в ваш список вместо :, а другой элемент заменяет [], поэтому мы получаем

foldr f x [1,2,3,4]
——>
foldr f x (1:(2:(3:(4:[]))))
——>
f 1 (f 2 (f 3 (f 4 x)))

Итак, как мы можем делать то, что мыхотите (по существу реализовать takeWhile с foldr), тщательно выбирая нашу функцию?Ну, есть два случая:

1. Предикат верен для рассматриваемого элемента
2. Предикат ложен для рассматриваемого элемента

В случае1 нам нужно включить наш элемент в список, и поэтому мы можем попытаться сделать то же самое, что мы сделали с нашей функцией идентификации выше.

В случае 2 мы хотим не включать элемент и ничего не включать послеэто, так что мы можем просто вернуть [].

Предположим, что наша функция правильно работает с предикатом "меньше 3", вот как мы можем его оценить:

f 1 (f 2 (f 3 (f 4 x)))
--T    T    F    F   (Result of predicate)
-- what f should become:
1 : (2 : ([]         ))
——>
[1,2]

Итак, все, что нам нужно сделать, это реализовать f,Предположим, предикат называется p.Тогда:

f x xs = if p x then x : xs else []

А теперь мы можем написать

func p = foldr f [] where
  f x xs = if p x then x : xs else []