Концепция соответствия шаблонов Haskell за сплиттером текста - PullRequest
Новая
       44

Концепция соответствия шаблонов Haskell за сплиттером текста

1 голос
/ 06 февраля 2012

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

 split :: String -> Char -> [String]
 split [] delim = [""]
 split (c:cs) delim
     | c == delim = "" : rest
     | otherwise = (c : head rest) : tail rest
       where
         rest = split cs delim

Я знаю, что head возвращает 1-й элемент списка, а tail возвращает остаток.Но я все еще не могу понять функциональность этого.Это берет строку и разбивает ее на список строк из данного символа.

1 Ответ

3 голосов
/ 06 февраля 2012

Возможно, это будет понятнее в следующей форме: 

split [] delim = [""]    -- a list containing only an empty String
split (c:cs) delim = let (firstWord:moreWords) = split cs delim
                     in if c == delim
                           then "" : firstWord : moreWords
                           else (c:firstWord) : moreWords

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

Например, оценка split "abc cde" ' ' происходит как 

split "abc cde" ' '
    ~> 'a' == ' ' ? No, next guard
    ~> ('a' : something) : somethingElse

, где something и somethingElse будут определены позже, разделив остаток "bc cde". After looking at the first character, it's been determined that whatever the final result is, its first entry starts with 'a'`. Продолжая определять остальное, 

split "bc cde" ' '
    ~> ('b' : something1) : somethingElse1
       where (something1 : somethingElse1) = split "c cde" ' '

Итак, теперь первые два символа первой записи результата известны. Затем из следующего шага определяется, что something1 начинается с 'c'. Затем, наконец, мы достигаем разделитель, то есть тот случай, когда первый элемент результата определяется без ссылки на более поздние рекурсивные вызовы, и в рекурсии остается только остаток результата.

Другой способ сформулировать алгоритм (спасибо @ dave4420 за предложение) 

split input delim = foldr combine [""] input
  where
    combine c rest@(~(wd : wds))
        | c == delim = "" : rest
        | otherwise  = (c : wd) : wds
...