Тщательно разработанная неизменность позволяет избежать ненужного обновления
Неизменяемые структуры данных являются проблемой эффективности только в том случае, если они постоянно меняются или вы создаете их неправильно. Например, непрерывное добавление большего числа в конец растущего списка является квадратичным, тогда как объединение списка списков является линейным. Если вы тщательно обдумаете, вы обычно можете разумно построить свою структуру, и ваш друг - ленивая оценка - дайте обещание разобраться и перестаньте беспокоиться.
Слепая попытка воспроизвести императивный алгоритм может быть неэффективной, но вы ошибаетесь в своем утверждении, что функциональное программирование здесь должно быть асимптотически плохим.
Пример: чисто функциональный GEP: обозначение Карвы в линейном времени
Я буду придерживаться вашего примера разбора записи Karva для GEP. (
Я играл с этим решением более полно в этом ответе .)
Вот довольно чисто чисто функциональное решение проблемы. Я воспользуюсь возможностью назвать несколько хороших общих схем рекурсии по пути.
код
(импорт Data.Tree расходных материалов data Tree a = Node {rootLabel :: a, subForest :: Forest a}, где type Forest a = [Tree a].)
import Data.Tree
import Data.Tree.Pretty -- from the pretty-tree package for visualising trees
arity :: Char -> Int
arity c
| c `elem` "+*-/" = 2
| c `elem` "Q" = 1
| otherwise = 0
Гиломорфизм - это композиция анаморфизма (наращивание, раскрытие) и катаморфизма (объединение, складывание).
Эти термины представлены сообществу FP в оригинальной статье Функциональное программирование с бананами, линзами и колючей проволокой .
Мы собираемся вытащить уровни (ана / развернуть) и объединить их вместе (ката / фолд).
hylomorphism :: b -> (a -> b -> b) -> (c -> (a, c)) -> (c -> Bool) -> c -> b
hylomorphism base combine pullout stop seed = hylo seed where
hylo s | stop s = base
| otherwise = combine new (hylo s')
where (new,s') = pullout s
Чтобы вытащить уровень, мы используем общую арность с предыдущего уровня, чтобы найти, где отделить этот новый уровень, и передаем общую арность для этого уровня, готового для следующего раза:
pullLevel :: (Int,String) -> (String,(Int,String))
pullLevel (n,cs) = (level,(total, cs')) where
(level, cs') = splitAt n cs
total = sum $ map arity level
Чтобы объединить уровень (в виде строки) с уровнем ниже (это уже лес), мы просто извлекаем количество деревьев, необходимое каждому персонажу.
combineLevel :: String -> Forest Char -> Forest Char
combineLevel "" [] = []
combineLevel (c:cs) levelBelow = Node c subforest : combineLevel cs theRest
where (subforest,theRest) = splitAt (arity c) levelBelow
Теперь мы можем разобрать Карву, используя гиломорфизм. Обратите внимание, что мы заполняем его с полной арностью вне строки 1, поскольку на корневом уровне есть только один узел. Соответственно, мы применяем head к результату, чтобы вернуть этот синглтон после hylomorphism.
karvaToTree :: String -> Tree Char
karvaToTree cs = let
zero (n,_) = n == 0
in head $ hylomorphism [] combineLevel pullLevel zero (1,cs)
Линейное время
Здесь нет ни экспоненциального увеличения, ни повторного поиска O (log (n)), ни дорогостоящих модификаций, поэтому у нас не должно быть особых проблем.
arity - это O (1) splitAt part - это O (part) pullLevel (part,cs) - это O (part) для захвата, используя splitAt для получения level, плюс O (part) для map arity level, поэтому O (part) combineLevel (c:cs) - это O (arity c) для splitAt и O (sum $ map arity cs) для рекурсивного вызова hylomorphism [] combineLevel pullLevel zero (1,cs)
- делает
pullLevel вызов для каждого уровня, поэтому общая стоимость pullLevel составляет O (sum частей) = O (n)
- делает
combineLevel вызов для каждого уровня, поэтому общая стоимость combineLevel равна O (sum $ map arity уровней) = O (n), поскольку общая арность всего ввода ограничена n для допустимых строк.
- делает O (#levels) вызовы
zero (что является O (1)), а #levels связан n, так что это тоже ниже O (n)
Следовательно, karvaToTree является линейным по длине входа.
Я думаю, что это подтверждает утверждение, что вам нужно было использовать изменчивость, чтобы получить здесь линейный алгоритм.
Демо
Давайте подведем итоги (так как дерево настолько полно синтаксиса, что трудно прочитать вывод!). Вы должны cabal install pretty-tree, чтобы получить Data.Tree.Pretty.
see :: Tree Char -> IO ()
see = putStrLn.drawVerticalTree.fmap (:"")
ghci> karvaToTree "Q/a*+b-cbabaccbac"
Node {rootLabel = 'Q', subForest = [Node {rootLabel = '/', subForest = [Node {rootLabel = 'a', subForest = []},Node {rootLabel = '*', subForest = [Node {rootLabel = '+', subForest = [Node {rootLabel = '-', subForest = [Node {rootLabel = 'b', subForest = []},Node {rootLabel = 'a', subForest = []}]},Node {rootLabel = 'c', subForest = []}]},Node {rootLabel = 'b', subForest = []}]}]}]}
ghci> see $ karvaToTree "Q/a*+b-cbabaccbac"
Q
|
/
|
------
/ \
a *
|
-----
/ \
+ b
|
----
/ \
- c
|
--
/ \
b a
, который соответствует выводу, ожидаемому от этого урока, где я нашел пример :
