Реализация сгибов в Haskell - PullRequest
Новая
       31

Реализация сгибов в Haskell

1 голос
/ 24 марта 2019

У меня много проблем, пытаясь понять реализацию складок на Haskell. Мне нужно иметь две функции, использующие Fold, которые имеют этот вывод 

> runLengthEncode "aaaaaaabbb"
[(7,'a'),(3,'b')]
> runLengthDecode [(1,'h'), (5,'i')]
"hiiiii"

Итак, я сначала написал функцию, как я делал бы с сопоставлением с образцом (они работают), но теперь я не знаю, как «перевести» это, используя либо сворачивание влево, либо сворачивание вправо. 

runLengthEncode :: String -> [(Int,Char)]
runLengthEncode [] = []
runLengthEncode (x:xs) = runLengthEncode 1 x xs
    where
        runLengthEncode n x [] = [(n,x)]
        runLengthEncode n x (y:ys) | x == y = runLengthEncode (n + 1) y ys
                                   | otherwise = (n,x) : runLengthEncode 1 y ys

runLengthDecode :: [(Int,Char)] -> String
runLengthDecode [] = []
runLengthDecode ((a,b):xs) = replicate a b ++ (runLengthDecode xs)

1 Ответ

8 голосов
/ 24 марта 2019

Думайте о фолде как о наборе терминов: 

[a,b,c,d]

и добавление начального значения zz и двоичного оператора <+> между терминами: 

foldl (<+>) zz [a,b,c,d] = (((zz <+> a) <+> b) <+> c) <+> d
foldr (<+>) zz [a,b,c,d] = a <+> (b <+> (c <+> (d <+> zz)))

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

Итак, чтобы выразить runLengthEncode как сгиб справа, вам нужно: 

'a' <+> ('a' <+> ('a' <+> ('b' <+> zz))) = [(3,'a'),(1,'b')]

для оператора <+> и некоторого начального значения zz.

Мы можем легко «решить» для zz, потому что мы знаем, что runLengthEncode [] = [], поэтому zz = []. Нам нужно определить <+>, чтобы он удовлетворял уравнениям, полученным из примера выше (работает справа налево), например: 

'b' <+> [] = [(1, 'b')]
'a' <+> [(1, 'b')] = [(1, 'a'), (1, 'b')]
'a' <+> [(1, 'a'), (1, 'b')] = [(2, 'a'), (1, 'b')]
'a' <+> [(2, 'a'), (1, 'b')] = [(3, 'a'), (1, 'b')]

Определить такого оператора на самом деле довольно просто: 

(<+>) :: Char -> [(Int, Char)] -> [(Int, Char)]
x <+> ((n, y) : rest) | x == y = ((n+1), y) : rest
x <+> rest                     = (1, x) : rest

так мы получаем: 

runLengthEncode' :: String -> [(Int,Char)]
runLengthEncode' = foldr (<+>) []

Попробуйте сделать это и с левой складкой: 

(((zz + 'a') <+> 'a') <+> 'a') <+> 'b' =>  [(3,'a'),(1,'b')]

Вы обнаружите, что когда придет время для определения <+>, вам придется проверять последний элемент текущего RLE вместо первого. Конечно, это можно сделать, но это немного менее естественно, поэтому я использовал правый сгиб выше.

Для runLengthDecode это одно и то же дело: 

(1, 'h') <+> ((5, 'i') <+> zz) = "hiiiii"

Опять же, определите, каким должно быть zz. Затем выясните, как написать бинарный оператор для решения: 

(5, 'i') <+> zz = "iiiii"
(1, 'h') <+> "iiiii" = "hiiiii"

Спойлеры следуют ...

Конечно, вам на самом деле не нужно использовать синтаксис оператора, поэтому полное решение будет выглядеть так: 

runLengthEncode'' :: String -> [(Int,Char)]
runLengthEncode'' = foldr step []
  where step x ((n, y) : rest) | x == y = ((n+1), y) : rest
        step x rest                     = (1, x) : rest

runLengthDecode'' :: [(Int,Char)] -> String
runLengthDecode'' = foldr step ""
  where step (n, x) str = replicate n x ++ str
...