Изучение карт Haskell, складок, петель и рекурсии

Question

Я только что окунулся в мир Хаскелла, как часть моего путешествия по программированию (переходя от процедурного к ООП к параллельному и теперь функциональному).

Я пробовал онлайн Haskell Evaluator .

Однако я застрял в проблеме:

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

На процедурном языке это для меня достаточно просто (с использованием рекурсии) (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;
    }
}

Все очень хорошо, однако моя неудачная попытка на Хаскеле была такой:

let sum x = x+sum  in map sum [1..10]

это привело к следующей ошибке (с вышеупомянутого сайта):

Occurs check: cannot construct the infinite type: a = a -> t

Пожалуйста, имейте в виду, что я использовал Haskell только в течение последних 30 минут!

Я ищу не просто ответ, а более подробное объяснение.

Answer 1

Я ищу не просто ответ, а более подробное его объяснение.

С левой стороны от = вы используете sum как функцию, применяемую кx.Компилятор не знает тип x, поэтому компилятор использует переменную типа a для обозначения «типа x».На этом этапе компилятор также не знает тип результата функции sum, поэтому он выбирает другую переменную типа, этот тип t, для обозначения типа результата.Теперь с левой стороны компилятор считает, что тип x равен a -> t (функция принимает a и возвращает t).

На правой стороне = youдобавить x и sum.В Haskell можно добавлять все виды чисел, но вы можете добавлять два числа, только если они имеют тип одинаковый .Таким образом, здесь компилятор предполагает, что sum имеет тот же тип, что и x, а именно тип a.

Но в Haskell идентификатор имеет один тип - возможно, причудливый сложный тип, но, тем не менее, один тип.Это включает sum, тип которого должен быть одинаковым с обеих сторон знака `, поэтому компилятор пытается решить уравнение

a = a -> t

Нет значений для a и t, которые решают это уравнение. Это просто невозможно сделать.Не существует a такого, что a равно функции, которая принимает себя в качестве аргумента.Таким образом, возникает сообщение об ошибке

cannot construct the infinite type: a = a -> t

Даже со всеми объяснениями, это не такое большое сообщение об ошибке, не так ли?

Добро пожаловать в Haskell: -)

---

PS Возможно, вам понравится "Гелий для изучения Haskell", который дает гораздо более приятные сообщения об ошибках для начинающих.

Answer 2

'sum' принимает список значений и сводит его к одному значению.Вы можете написать его как явный цикл (помните, что в 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

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

Я бы посоветовал вам начать с введения в Haskell, возможно, " Программирование на Haskell ", чтобы почувствовать основные концепции функционального программирования.Другие хорошие вводные материалы описаны в этом вопросе .

Answer 3

Вам нужно прочитать хороший учебник, есть много серьезных недоразумений.

Сначала я собираюсь предположить, что вы имеете в виду списки, а не массивы.В Haskell существуют массивы, но вы не столкнетесь с ними на начальном уровне.(Не говоря уже о том, что вы используете [1..10], который представляет собой список чисел от 1 до 10).

Функция, которую вы хотите, фактически встроена и называется суммой, так что мы получимчтобы назвать что-то еще, new_sum:

new_sum [] = 0
new_sum (h:t) = h + (sum t)

Answer 4

Давайте посмотрим на первую часть этого:

let sum x = x+sum 

Каким будет тип суммы в этом случае? Он принимает число и возвращает функцию, которая принимает число, которое возвращает функцию, которая принимает число и т. Д., Если вы написали это пусть сумма х = + х у вас была бы функция, которая принимает число и возвращает функцию + x. а также пусть сумма = + вернет функцию, которая берет два целых числа и добавляет их.

так что теперь давайте посмотрим на вторую часть. в сумме карты [1..10] Карта принимает функцию с одним аргументом и применяет ее к каждому элементу списка. Там нет места, чтобы вставить аккумулятор, поэтому давайте рассмотрим другие функции списка, в частности, foldl, foldr. оба они принимают функцию двух аргументов: список и начальное значение. Разница между Foldl и Foldr находится на той стороне, с которой они начинаются. Я остался 1 + 2 + 3 и т. д., а r прав 10 + 9 + 8 и т.д.

let sum = (+) в кратной сумме 0 [1..10]