Может ли кто-нибудь объяснить мне эти функции на Хаскеле? - PullRequest
Новая
       9

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

2 голосов
/ 26 мая 2009

В прошлом я баловался с Хаскеллом, недавно всерьез занялся этим, и я читаю Хаскелл из реального мира. Некоторые из приведенных ими примеров я еще не понял. Вот так вот: 

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'

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

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

РЕДАКТИРОВАТЬ: Я знаю, это был сбой копирования-вставки. К сожалению.

РЕДАКТИРОВАТЬ 2: Кажется, моя путаница заключалась в том, что эти функции на самом деле / ​​возвращают / у меня все это работает сейчас. Спасибо за ответы, ребята, это наконец-то щелкнуло! Я ценю это!

Ответы [ 5 ]

10 голосов
/ 26 мая 2009

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

myLength [] = 0

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

myLength [1,2,3]

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

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

, что составляет 3.

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

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

Для визуализации, скажем, у вас есть строка "foo \ nbar \ r \ nbaz".

Итак, при звонке результат будет: 

[ 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

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

4 голосов
/ 26 мая 2009

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

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

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

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

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

2 голосов
/ 26 мая 2009

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

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

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

2 голосов
/ 26 мая 2009

Re: myLength (x:xs) = 1 + myLength (xs) - это «половина» определения myLength, в соответствии с сопоставлением с шаблоном говорится, что , если аргумент имеет голову и хвост, то результат на один больше, чем рекурсивный хвостовой вызов на хвосте - должна быть другая половина, чтобы сказать, что результат равен 0, когда аргумент не может соответствовать x:xs, т. е. когда аргумент представляет собой пустой список.

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

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

1 голос
/ 26 мая 2009

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

myLength :: [a] -> Int

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

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

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

...