Пример рекурсивной функции Haskell с foldr

Question

Я начал изучать Haskell снова, после короткого перерыва, и в настоящее время я пытаюсь лучше понять, как рекурсия и лямбда-выражения работают в Haskell.

В этом: YouTube video, есть функция пример того, что озадачивает меня гораздо больше, чем это, вероятно, следует, с точки зрения того, как она на самом деле работает:

firstThat :: (a -> Bool) -> a -> [a] -> a 
firstThat f = foldr (\x acc -> if f x then x else acc) 

Ради ясности и с тех пор не было сразу очевидно для меня, я приведу пример применения этой функции некоторые аргументы:

firstThat (>10) 2000 [10,20,30,40] --returns 20, but would return 2000, if none of the values in the list were greater than 10 

Пожалуйста, поправьте меня, если мои предположения неверны.

кажется firstThat принимает три аргумента:

1. функцию, которая принимает один аргументы и возвращает логическое значение. Поскольку оператор > фактически является функцией infix, первый аргумент в приведенном выше примере кажется результатом частичного приложения к функции > - это правильно?
2. неопределенное значение того же типа, как ожидается, как отсутствующий аргумент функции, представленной в качестве первого аргумента
3. список значений вышеупомянутого типа

Но фактической функции firstThat, кажется, определяется по-разному из его объявления типа, с одним аргументом. Поскольку foldr обычно принимает три аргумента, которые я собрал, происходит какое-то частичное приложение. Лямбда-выражение, представленное в качестве аргумента foldr, похоже, также не содержит аргументов.

Итак, как именно эта функция работает? Прошу прощения, если я слишком плотный или не вижу лес для деревьев, но я просто не могу обмотать голову вокруг него, что разочаровывает.

Любое полезное объяснение или пример (ы) были бы весьма признательны.

Спасибо!

Answer 1

Но фактическая функция firstThat, кажется, определяется по-разному от его типа декларации, только с одним аргументом. Поскольку foldr обычно принимает три аргумента, которые я собрал, происходит какое-то частичное приложение.

Вы правы. Тем не менее, есть более хороший способ сделать это, чем говорить о «отсутствующих аргументах» - тот, который не заставляет вас спрашивать, куда они ушли. Вот два способа, в которых аргументы отсутствуют.

Во-первых, рассмотрим эту функцию:

add :: Num a => a -> a -> a 
add x y = x + y 

Как вы знаете, мы можем определить его следующим образом:

add :: Num a => a -> a -> a 
add = (+) 

Это работает, потому что функции Haskell являются такие ценности, как и любой другой. Мы можем просто определить значение, add, как равное другому значению, (+), которое просто является функцией. Для объявления функции не требуется специального синтаксиса.Результатом является то, что написание аргументов явно (почти) никогда не требуется; основная причина, почему мы это делаем, потому что она часто делает код более читаемым (например, я мог бы определить firstThat без записи параметра f явно, но я этого не сделаю, потому что результат довольно отвратительный).

Во-вторых, всякий раз, когда вы видите тип функции с тремя аргументами ...

firstThat :: (a -> Bool) -> a -> [a] -> a 

... Вы также можете прочитать его, как это ...

firstThat :: (a -> Bool) -> (a -> [a] -> a) 

... то есть , функция одного аргумента, создающая функцию из двух аргументов. Это работает для всех функций более чем одного аргумента. Ключевым выводом является то, что в глубине все функции Haskell принимают только один аргумент. Вот почему работает частичное приложение. Так, увидев ...

firstThat :: (a -> Bool) -> a -> [a] -> a 
firstThat f = foldr (\x acc -> if f x then x else acc) 

... вы можете точно сказать, что вы написали явно все параметры, которые firstThat принимает - то есть, только один :)

---

лямбда выражение, представленное в качестве аргумента foldr, похоже, также не содержит аргументов.

Не совсем. foldr (когда ограничиваются перечнями) является ...

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

... и поэтому функция перешла к ней принимает два аргумента (не стесняйтесь добавлять воздушные кавычки «два», учитывая приведенные выше рассуждения). Лямбда была написана как ...

\x acc -> if f x then x else acc 

... с двумя явными аргументами, x и acc.

Answer 2

Функция, которая принимает один аргумент и возвращает логическое значение. Так как оператор> фактически является инфиксной функцией, первый аргумент в приведенном выше примере кажется результатом частичного приложения к функции> - это правильно?

да: (>10) коротка для \x -> x > 10, так же, как (10>) будет коротким для \x -> 10 > x.

неопределенное значение того же типа, как ожидается, как отсутствующий аргумент функции, представленной в качестве первого аргумента

в первую очередь, это не хватают аргументов: опуская аргумент, вы получите значение функции. однако тип второго аргумента действительно соответствует аргументу функции >10, так же, как он соответствует типу элементов списка [10,20,30,40] (что является лучшим аргументом).

список значений вышеупомянутого типа

да.

Но фактическая функция firstThat кажется определенной иначе, чем ее объявление типа, с одним аргументом. Поскольку foldr обычно принимает три аргумента, которые я собрал, происходит какое-то частичное применение. Лямбда-выражение, представленное в качестве аргумента для foldr, похоже, также не содержит аргументов.

Это потому, что данный, например. foo x y z = x * y * z эти 2 строки эквивалентны:

bar x  = foo x 
bar x y z = foo x y z 

- это из-за концепции под названием выделки. Currying также является причиной того, что сигнатуры типа функции не являются (a, b) -> c, а вместо этого a -> b -> c, что в свою очередь эквивалентно a -> (b -> c) из-за правильной ассоциативности оператора типа ->.

Таким образом, эти две строки эквивалентны:

firstThat f  = foldr (\x acc -> if f x then x else acc) 
firstThat f x y = foldr (\x acc -> if f x then x else acc) x y 

---

Примечание:, что вы также можете использовать Data.List.find в сочетании с Data.Maybe.fromMaybe:

λ> fromMaybe 2000 $ find (>10) [10, 20, 30] 
20 
λ> fromMaybe 2000 $ find (>10) [1, 2, 3] 
2000 

---

Смотри также:

• https://en.wikipedia.org/wiki/Currying.
• https://www.fpcomplete.com/user/EFulmer/currying-and-partial-application
• http://learnyouahaskell.com/higher-order-functions