Определение сгибания в терминах сгибания - PullRequest
Новая
       71

Определение сгибания в терминах сгибания

0 голосов
/ 30 октября 2018 
myFoldl :: (a -> b -> a) -> a -> [b] -> a

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

Я сейчас читаю книгу о Хаскеле. И в нем он написал свою собственную версию функции foldl, но в терминах foldr. Я не следую.

  1. Почему существует 4 аргумента для foldr?
  2. Что делает функция id?

Ответы [ 2 ]

0 голосов
/ 30 октября 2018

Дело станет очевидным, когда развернуть выражение foldr step id xs z:

Как сказал Адам Смит в комментариях:

идентификатор шага сворачивания xs z = (идентификатор шага сворачивания xs) z

Рассмотрим foldr step id xs сначала 

foldr step id xs
= x1 `step` (foldr step id xs1)
= x1 `step` (x2 `step` (foldr step id xs2))
...
= x1 `step` (x2 `step` ... (xn `step` (foldr step id []))...)
= x1 `step` (x2 `step` ... (xn `step` id)...)

, где 

xs = (x1:xs1)
xs1 = (x2:xs2), xs = (x1:x2:xs2) 
....
xsn = (xn:[]), xs = (x1:x2...xsn) respectively

Теперь примените вышеуказанную функцию с аргументом z, т.е. 

(x1 `step` (x2 `step` ... (xn `step` id)...)) z

и пусть 

g = (x2 `step` ... (xn `step` id)...)

дает 

(x1 `step` g) z
* * +1025 т.е. * * 1 026 
(step x1 g) z

и теперь примените часть к элементу foldl:

где шаг x g a = g (f a x)

дает 

(step x1 g) z = step x1 g z = g (step z x1)

, где 

g (step z x1) = (x2 `step` (x3 step ... (xn `step` id)...) (step z x1)

пусть 

g' = (x3 step ... (xn `step` id)...)

дает 

(x2 `step` g') (step z x1)
= step x2 g' (step z x1)
= g' (step (step z x1) x2))
= (x3 step ... (xn `step` id)...) (step (step z x1) x2))

повторяет те же шаги, наконец, у нас, 

(xn `step` id) (step ....(step (step z x1) x2)....)
= step xn id (step ....(step (step z x1) x2)....)
= id (step (step ....(step (step z x1) x2)....) xn)
= (step (step ....(step (step z x1) x2)....) xn)
= foldl step z xs

и теперь, очевидно, зачем использовать функцию id. наконец, понять, почему 

foldl step z xs = (step (step ....(step (step z x1) x2)....) xn)

начальный регистр: 

foldl step z' [] = z'

рекурсивный случай: 

foldl step z (x1:xs1) 
= foldl step (step z x1) xs1
= foldl step (step (step z x1) x2) xs2
...
= foldl step (step (step ....(step (step z x1) x2)....) xn) []
= (step (step ....(step (step z x1) x2)....) xn)

, где 

z' = (step (step ....(step (step z x1) x2)....) xn) in initial case

Так же, как и выше.

0 голосов
/ 30 октября 2018

Как говорит Адам Смит в комментариях, есть только три аргумента foldr. Рассматриваемая строка разбирается так: 

myFoldl f z xs = (foldr step id xs) z

Конечно, есть и другие неявные скобки, но это важные.

Здесь мы переписываем аннотации типов, предполагая, что переменные типа области действия (т. Е. a и b означают одинаковые типы во всем этом определении). 

myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z xs =  goFold z
   where
      goFold :: a -> a
      goFold = foldr step id xs
      step :: b -> (a -> a) -> (a -> a)  -- Last brackets are redundant
      step x g a = g (f a x)

Я переместил вызов foldr в отдельное значение goFold, чтобы вы могли видеть его тип и то, как он применяется к значению z. Функция step накапливает значения b в функцию типа (a -> a). Каждое значение b, обработанное goFold, добавляет дополнительное из них. «Ноль» для функций, конечно, id из прелюдии: 

id :: a -> a
id x = x

Оператор функции -> в типах является ассоциативным справа, поэтому последняя пара скобок в типе step является избыточной. Но я написал это так, потому что это подчеркивает способ использования step; он принимает значение и функцию и возвращает новую функцию.

...