Изучая карты Haskell, сгибы, циклы и рекурсию
Я только что опустил палец ноги в мир Haskell как часть своей поездки программирования просвещения (идущий дальше от, процедурный к ООП к параллельному к теперь функциональному).
Я пробовал Средство анализа Haskell онлайн.
Однако я теперь застреваю на проблеме:
Создайте простую функцию, которая дает полную сумму массива чисел.
На процедурном языке это для меня достаточно легко (использование рекурсии) (c#):
private int sum(ArrayList x, int i)
{
if (!(x.Count < i + 1)) {
int t = 0;
t = x.Item(i);
t = sum(x, i + 1) + t;
return t;
}
}
Все очень прекрасные однако моя неудачная попытка в Haskell были таким образом:
let sum x = x+sum in map sum [1..10]
это привело к следующей ошибке (с того вышеупомянутого веб-сайта):
Occurs check: cannot construct the infinite type: a = a -> t
Примите во внимание, что я только использовал Haskell в течение прошлых 30 минут!
Я просто не ищу ответ, но больше объяснения его.
4 ответа
Я ищу не просто ответ, а более подробное его объяснение.
В левой части = используется сумма как функция, применяемая к x . Компилятору неизвестен тип x , поэтому компилятор использует переменную типа a для обозначения «типа x ». На этом этапе компилятор также не знает тип результата функции sum , поэтому он выбирает переменную другого типа, этот тип t , чтобы заменить тип результата. Теперь в левой части компилятор считает, что тип x равен a -> t (функция принимает a и возвращает t ]).
В правой части = вы добавляете x и сумму . В Haskell можно складывать все виды чисел, но вы можете складывать два числа только в том случае, если они имеют тот же тип . Итак, здесь компилятор предполагает, что sum имеет тот же тип, что и x , а именно тип a .
Но в Haskell идентификатор имеет один тип - может быть, довольно сложный тип, но, тем не менее, один тип. Сюда входит сумма , тип которой должен быть одинаковым по обе стороны от знака `, поэтому компилятор пытается решить уравнение
a = a -> t
. Нет значений для a и ] t , которые решают это уравнение. Это просто невозможно. Не существует a такого, что a равняется функции, которая принимает себя в качестве аргумента.Таким образом возникает сообщение об ошибке
cannot construct the infinite type: a = a -> t
Даже несмотря на все объяснения, это не такое уж большое сообщение об ошибке, не так ли?
Добро пожаловать в Haskell: -)
P.S. Возможно, вам понравится попробовать «Гелий для изучения Haskell», который дает гораздо более приятные сообщения об ошибках для новичков.
Вам нужно прочитать хороший учебник, здесь есть ряд больших недоразумений.
Сначала я предположу, что вы имеете в виду списки, а не массивы. Массивы существуют в Haskell, но это не то, с чем вы столкнетесь на начальном уровне. (Не говоря уже о том, что вы используете [1..10], который является списком чисел от 1 до 10).
Функция, которая вам нужна, на самом деле встроена и называется sum, поэтому нам придется назвать нашу функцию как-то иначе, new_sum:
new_sum [] = 0
new_sum (h:t) = h + (sum t)
Давайте посмотрим на первую часть этого:
let sum x = x+sum
Каким будет тип суммы в этом случае? Он принимает число и возвращает функцию, которая принимает число, которое возвращает функцию, которая принимает число и т. Д., Если вы его написали. пусть сумма x = + x у вас будет функция, которая принимает число и возвращает функцию + x. а также пусть сумма = + вернет функцию, которая берет два целых числа и складывает их.
Итак, теперь давайте посмотрим на вторую часть. в сумме карты [1..10] map принимает функцию одного аргумента и применяет ее к каждому элементу списка. Там нет места, чтобы вклинить аккумулятор, поэтому давайте рассмотрим другие функции списков, в частности foldl, foldr. оба они принимают функцию двух аргументов: списка и начального значения. Разница между foldl и foldr заключается в том, с какой стороны они начинаются. l слева, поэтому 1 + 2 + 3 и т. д. и r справа 10 + 9 + 8 и т.д.
пусть sum = (+) в кратной сумме 0 [1..10]
«сумма» принимает список значений и сокращает его до одного значения. Вы можете написать его как явный цикл (помните, что Haskell не имеет ключевых слов цикла, но использует рекурсию). Обратите внимание, как определение состоит из двух частей, в зависимости от формы списка:
mysum [] = 0
mysum (x:xs) = x + mysum xs
Или, что более эффективно, в стиле хвостовой рекурсии :
mysum xs = go 0 xs
where
go n [] = n
go n (x:xs) = go (n+x) xs
Однако в Haskell есть богатая библиотека управляющих структур, которые работать с ленивыми списками. В этом случае сокращение списка до одного значения может быть выполнено с помощью функции сокращения: сворачивания.
Итак, mysum можно записать как:
mysum xs = foldr (+) 0 xs
Например:
Prelude> foldr (+) 0 [1..10]
55
Ваша ошибка заключалась в использовании карты , которая преобразует список, по одному элементу за раз, а не сложить .
Я бы посоветовал вам начать с введения в Haskell, возможно, « Программирование на Haskell », чтобы понять основные концепции функционального программирования. Другие хорошие вводные материалы описаны в этом вопросе.