Реализация foreach в haskell для начинающих / учеников

Question

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

Не могли бы вы исправить меня? Я хочу, чтобы морфизм foreach принимал список a и морфизм f в качестве аргументов и возвращал список всех результатов r из f, примененных ко всем a элементам.

foreach :: [a] → f → [r]
foreach [] f = []
foreach x:[] f = (f x):[]
foreach []:x f = []:(f x)
foreach (x:xs) f = (f x) : (foreach (xs f))

При компиляции у меня есть src\Main.hs:23:0: Parse error in pattern

Answer 1

Проблема синтаксическая, в этой строке:

foreach x:[] f = (f x):[]

Приложение-конструктор в шаблонах обычно необходимо заключить в скобки. Это будет работать:

foreach (x:[]) f = (f x):[]

Между прочим ... применение функции имеет наивысший приоритет, поэтому с другой стороны вам не нужны скобки справа:

foreach (x:[]) f = f x:[]

Вышеприведенное справедливо для любого инфиксного конструктора, но, как последнее замечание, для списков, в частности, существует специальный синтаксис:

foreach [x] f = [f x]

Есть другие проблемы с вашим кодом в его нынешнем виде, но это немедленная ошибка. Краткий обзор других проблем:

foreach :: [a] → f → [r]

Переменные типа неявно определяются количественно, поэтому это означает любой тип f. Вам нужен более конкретный тип, а именно a -> r.

foreach x:[] f = (f x):[]

В этом нет необходимости - рекурсивный регистр здесь будет работать правильно, применяя f к x и вызывая себя в хвост, давая пустой список списка.

foreach []:x f = []:(f x)

Я не думаю, что это означает, что вы думаете, что это означает - это шаблон, сопоставляющий заголовок списка пустому списку [], подразумевая, что функция работает со списком списков.

foreach (x:xs) f = (f x) : (foreach (xs f))

Скобки здесь либо не нужны, либо неверны. Опять же, приложение функции имеет более высокий приоритет, чем операторы типа :. Кроме того, (xs f) означает применение xs к f, как если бы это была функция. Чтобы применить foreach к двум аргументам, достаточно просто foreach xs f.

---

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

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

Answer 2

Подпись типа, которую вы даете, является (по крайней мере, по мнению компилятора Haskell) фиктивной. Это функция, которая принимает список элементов любого a и значения any type f и выдает список значений any type r. Это как сказать: «У меня есть слон и отвертка. Преврати каждого слона в манго».

Похоже, ваша цель - реализовать функцию map:

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

Конечно, совершенно правильно перебрасывать аргументы:

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

Ваша реализация довольно близка, но есть несколько проблем.

Самое важное - помнить, что вы работаете с списками , а не массивами . Оператор :, также известный как «cons», берет элемент и добавляет его в список (например, 1 : [2,3,4]). Вы не можете использовать его для произвольной конкатенации элементов и списков, как в []:(f x). Существует оператор ++, который объединяет два списка (например, [f x] ++ xs, что совпадает с (f x) : xs), но вам не нужно использовать его для реализации foreach.

Наконец, (foreach (xs f)) не делает то, о чем вы думаете. Это не похоже на foreach(xs,f) в языке C, это похоже на foreach(xs(f)). (xs f) само по себе похоже на использование xs в качестве функции и применение f в качестве аргумента. Вместо этого вы хотите (foreach xs f).

Я остановлюсь здесь, чтобы не отдавать слишком много. Однако, один маленький кусочек: приложение функции имеет более высокий приоритет, чем любой оператор, поэтому вместо (f x) : (foreach xs f) вы можете сказать f x : foreach xs f.

Answer 3

Вы забыли поместить () в foreach []:x f = []:(f x) и неправильно указали тип функции, теперь должно скомпилироваться следующее:

foreach :: [a] -> (a -> r) -> [r]
foreach [] f = []
foreach (x:[]) f = (f x):[]
foreach (x:xs) f = (f x) : (foreach xs f)

и запустить:

*Main> foreach [1..20] (+1)
[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21]