Как работает определение scanr с точки зрения папки?

Упражнение 1 на странице 102 Викибука по Haskell предлагает: «Напишите собственное определение scanr, сначала используя рекурсию, а затем используя foldr». Я написал рекурсивный:

myscan f acc []     = [acc]
myscan f acc (x:xs) = val : rest where
    val  = f x (head rest)
    rest = myscan f acc xs

... но не смог определить версию папки. В конце концов я погуглил и нашел этот ответ:

myscan2 f acc xs = foldr f' [acc] xs where
    f' x xs = (f x (head xs)) : xs

Очевидно, что это работает, но для меня это не имеет смысла. Использование параметров

(+) 0 [1,2,3]

... становится примерно так:

myscan2 (+) 0 [1,2,3] = foldr f' [0] [1,2,3] where
    f' [0] [1,2,3] = ((+) [0] (head [1,2,3])) : [1,2,3]

... но часть ((+) [0] (head [1,2,3])) не совместима по типу с (+). Тем не менее, функция работает, так что я неправильно читаю или конвертирую?


fold haskell
person 0penStack    schedule 21.02.2015    source источник
comment
Это простая ошибка преобразования, вероятно, из-за их глупых имен аргументов. Должно быть ((+) 3 (head [0])) : [0]. Аккумулятор является вторым входом в функцию foldr, но по какой-то безумной причине они называют аргумент аккумулятора xs.   -  person genisage    schedule 22.02.2015

Ответы (1)


arrow_upward
3
arrow_downward

Дело в функции, которую вы нашли:

  1. xs на myscan2 f acc xs = foldr f' [acc] xs отличается от
    f' x xs = (f x (head xs)) : xs.

Они совершенно разные. Возможно, вы могли бы лучше понять, если бы это выглядело так:

myscanr f acc xs = foldr f' [acc] xs
     where f' b a = (f b (head a)) : a

Что он делает, изменяет аккумулятор на список, потому что сканирование накапливается, но сохраняет весь путь, проходящий через исходный список. Итак, f' cons (:) новая голова применяет функцию f к фактическому элементу списка и head аккумулятора.

person David Lilue    schedule 21.02.2015
comment
Очевидно, вы должны применить reverse, потому что возвращаемый список является обратным. - person David Lilue; 22.02.2015
comment
Я не думаю, что это назад. В конце концов, это правильный скан. Кроме того, вы переименовали x в b, и я думаю, что оставить его как x было бы более разумно. - person dfeuer; 22.02.2015
comment
Ты прав. Я ошибся :/ его scanr, но я переименовал оба, чтобы показать, что f' не имеет прямого отношения к переменной в myscanl f acc xs = foldr f' [acc] xs (они могут быть названы по вашему желанию). Конечно, его хорошее имя b как x и создает больше семантики. - person David Lilue; 22.02.2015
comment
Я бы не назвал это myscanl, когда это scanr! - person dfeuer; 22.02.2015
comment
Спасибо тебе за это. Я могу проследить работу на бумаге, хотя я пока не могу мысленно это понять. С нетерпением жду, когда это перестанет быть непостижимой инопланетной символикой загадочного значения. :) - person 0penStack; 22.02.2015
comment
Начало сложное, переключать контекст (императив -> функциональный). Я думаю, это ваш случай, как и другие, и я в том числе. Но позже функциональная парадигма более естественна. И система типов Haskell прекрасна. Если он компилируется, запускается - person David Lilue; 22.02.2015