Может ли кто-нибудь объяснить мне эти функции Haskell?

Question

В прошлом я увлекался Haskell, а недавно вернулся к нему всерьез, и я читаю real world haskell.Некоторые из примеров, которые они привели, мне еще предстоит понять.Такой в этом:

myLength []     = 0
myLength (x:xs) = 1 + myLength (xs)

Я не понимаю, как это работает, что такое 1 на самом деле тоже добавляется?Как рекурсия возвращает что-то, к чему можно добавить?Я этого не понимаю.

И вот у нас есть этот:

splitLines [] = []
splitLines cs =
       let (pre, suf) = break isLineTerminator cs
       in  pre : case suf of 
                   ('\r':'\n':rest) -> splitLines rest
                   ('\r':rest)      -> splitLines rest
                   ('\n':rest)      -> splitLines rest
                   _                -> []

isLineTerminator c = c == '\r' || c == '\n'

Как это работает, к чему на самом деле привязывается pre тоже?Я не понимаю, каким образом результат выражения case является чем-то, с чем pre может быть объединен.Может быть, мне просто нужно, чтобы кто-нибудь подробно объяснил оценку этих функций.Должно быть, я упускаю что-то очень важное.

Заранее спасибо!

Редактировать:Я знаю, это был сбой копирования-вставки.Извините.

ПРАВКА 2:Кажется, мое замешательство было связано с тем, какими на самом деле были эти функции / returning / Теперь у меня все получилось.Спасибо за ответы, ребята, наконец-то это сработало!Я ценю это!

Answer 1

Что касается первого, то это очень простой способ рекурсии.Однако, похоже, в нем отсутствует какая-то часть:

myLength [] = 0

Это работает путем одновременного удаления одного элемента из списка и добавления одного к результату.Чтобы визуализировать, рассмотрите вызов

myLength [1,2,3]

который будет оценивать, чтобы:

1 + myLength [2,3]
1 + 1 + myLength [3]
1 + 1 + 1 + myLength []
1 + 1 + 1 + 0

что равно 3.

Что касается второго, ну, вы уже разделили строку при следующем разрыве строки на две части:до и суф.Теперь suf будет начинаться либо с a , либо с a , либо с a .Мы хотим удалить их.Поэтому мы используем сопоставление с образцом.Посмотрите, как переменная rest по сути является переменной suf за вычетом начальных символов разрыва строки.

Итак, у нас есть pre, которая является первой строкой, и rest, которая является остальной частью текста.Итак, чтобы продолжить разбиение rest на строки, мы рекурсивно вызываем для него splitLines и объединяем результат с pre .

Для визуализации предположим, что у вас есть строка "foo bar baz".

Таким образом, при вызове результатом будет:

[ pre => foo, suf => \nbar\r\nbaz, rest => bar\r\n\baz ]
foo : splitLines bar\r\nbaz

затем splitLines вызывается снова, и результат расширяется в:

[ pre => bar, suf => \r\nbaz, rest = baz ]
foo : bar : splitLines baz

затем еще раз:

[ pre => baz, suf => [], rest = [] ]
foo : bar : baz

что и является конечным результатом.

Answer 2

Я думаю, что определение myLength пропускает случай, когда список пуст:

myLength [] = 0
myLength (x:xs) = 1 + myLength (xs)

С помощью этого определения, myLength из пустого списка равно 0.В (x:xs) паттен распаковывает список в первый элемент, a, и список с остальными элементами, xs.Если в списке есть один элемент, то xs это пустой список, поэтому результат равен 1 + 0.И так далее.

Рекурсию легче всего понять, когда вы сначала смотрите на базовый вариант, а затем видите, как каждый уровень рекурсии основывается на результате.(Базовый случай - это случай, когда функция не вызывает саму себя.Если рекурсивная функция не имеет базового варианта, результат будет бесконечным.)

Во втором примере базовый вариант (последний вариант в регистре case-statment) также является пустым списком.Таким образом, pre всегда будет добавлен к списку, что приведет к созданию нового, более длинного списка.

Answer 3

Ре: myLength (x:xs) = 1 + myLength (xs) -- это "половина" определения myLength, это говорит, по совпадению с шаблоном, что если аргумент имеет начало и конец, тогда результат на единицу больше, чем при рекурсивном вызове tail для tail - должна быть еще половина, чтобы сказать, что результат равен 0, когда аргумент не может совпадать x:xs, т. е. когда аргументом является пустой список.

Во втором случае возможность сопоставления различных шаблонов просто немного увеличена epxlicit с помощью case.

Кстати, лень здесь не является ключевой проблемой - ML с нетерпеливой оценкой, но сопоставлением с шаблоном, очень похожим на Haskell, будет работать очень похоже.Похоже, сопоставление с шаблоном - это то, что вам действительно нужно освежить в памяти.

Answer 4

Прежде всего, первый пример должен быть таким (Редактировать: похоже, теперь вы это исправили):

myLength []     = 0
myLength (x:xs) = 1 + myLength (xs)

Это работает следующим образом:допустим, я даю ему список из трех элементов, он возвращает единицу плюс длину хвоста (которая равна единице плюс длина хвоста (которая равна единице плюс длина хвоста, (которая равна [] на данный момент), что равно 1), что равно w), что равно 3 (окончательный ответ).Возможно, вложенная скобка поможет вам понять это.;-)

Answer 5

Поучительно посмотреть, какими будут сигнатуры типов функций.Они могли бы быть:

myLength :: [a] -> Int

В myLength, 1 добавляется к результату рекурсивного вызова myLength, который является Int, что , в свою очередь , приводит к Int.

splitLines :: [Char] -> [[Char]]

В splitLines, pre (а [Char]) добавляется к результату оператора case, который, судя по обращениям, является либо результатом рекурсивного вызова splitLines, который является [[Char]];или пустой список.В обоих случаях, добавляя pre (а [Char]) приведет к [[Char]] в свою очередь.