Тщательно разработанная неизменяемость позволяет избежать ненужного обновления

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

Слепая попытка воспроизвести императивный алгоритм может оказаться неэффективным, но вы ошибаетесь в своем утверждении, что функциональное программирование здесь должно быть асимптотически плохим.

Пример: чистый функциональный GEP: нотация Карвы в линейном времени

Я буду придерживаться вашего примера анализа нотации Карвы для 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 в основополагающем документе Функциональное программирование с бананами, линзами и колючей проволокой.

Мы собираемся вытащить уровни (ана / разворачивание) и объединить их вместе (cata / fold).

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 к результату, чтобы вернуть этот синглтон после гиломорфизма.

karvaToTree :: String -> Tree Char
karvaToTree cs = let
  zero (n,_) = n == 0          
    in head $ hylomorphism [] combineLevel pullLevel zero (1,cs) 

Линейное время

Здесь нет экспоненциального взрыва, повторных поисков O (log (n)) или дорогостоящих модификаций, поэтому у нас не должно быть особых проблем.

• arity is O(1)
• splitAt part is 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)

  • makes a pullLevel call for each level, so the total pullLevel cost is O(sum parts) = 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  

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

Нет единого способа сделать это, это действительно нужно делать в каждом конкретном случае. Обычно я пытаюсь разбить их на более простые операции, используя свертывание и разворачивание, а затем оптимизировать оттуда. Как отмечали другие, случай декодирования Karva - это развертка дерева в ширину, поэтому я начал с treeUnfoldM_BF. Возможно, в Erlang есть аналогичные функции.

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

import Control.Monad.State.Lazy
import Data.Tree

type MaxArity = Int
type NodeType = Char

treeify :: MaxArity -> [Char] -> Tree NodeType
treeify maxArity (x:xs) = evalState (unfoldTreeM_BF (step maxArity) x) xs
treeify _ [] = fail "empty list"

step :: MaxArity -> NodeType -> State [Char] (NodeType, [NodeType])
step maxArity node = do
  xs <- get
  -- figure out the actual child node count and use it instead of maxArity
  let (children, ys) = splitAt maxArity xs
  put ys
  return (node, children)

main :: IO ()
main = do
 let x = treeify 3 "0138513580135135135"
 putStr $ drawTree . fmap (:[]) $ x
 return ()

Есть несколько решений, когда требуется изменяемое состояние в функциональном программировании.

1. Используйте другой алгоритм, решающий ту же проблему. Например. быстрая сортировка обычно считается изменяемой и поэтому может быть менее полезной в функциональной настройке, но сортировка слиянием обычно лучше подходит для функциональной настройки. Я не могу сказать, возможен ли этот вариант и имеет ли смысл в вашем случае.

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

В вашем случае я не уверен, что неизменяемость действительно приводит к узкому месту в производительности. Вы правы, (под) дерево будет воссоздано при обновлении, но реализация Erlang, вероятно, будет повторно использовать все поддеревья, которые не изменились, что приведет к сложности O (log n) для каждого обновления вместо O (1) с изменяемым состоянием . Кроме того, копируются не узлы деревьев, а ссылки на узлы, что должно быть относительно эффективным. Вы можете прочитать об обновлениях дерева в функциональной настройке, например, в тезис Окасаки или в его книге «Чисто функциональные структуры данных »на основе дипломной работы. Я бы попробовал реализовать алгоритм с неизменной структурой данных и переключиться на изменяемую, если у вас есть проблемы с производительностью.

Также см. Некоторые соответствующие вопросы SO здесь и здесь.

Думаю, я понял, как решить вашу конкретную проблему с деревьями K (общая проблема слишком сложна: P). Мое решение представлено в каком-то ужасном гибридном Python-подобном псудокоде (сегодня я очень медленно работаю с FP) но не меняет узел после того, как вы его создали (трюк заключается в построении дерева вверх дном)

Во-первых, нам нужно определить, какие узлы какому уровню принадлежат:

levels currsize nodes = 
    this_level , rest = take currsize from nodes, whats left
    next_size = sum of the arities of the nodes
    return [this_level | levels next_size rest]
(initial currsize is 1)

Итак, в примере +/*abcd это должно дать вам [+, /*, abcd]. Теперь вы можете преобразовать это в дерево снизу вверх:

curr_trees = last level
for level in reverse(levels except the last)
    next_trees = []
    for root in level:
        n = arity of root
        trees, curr_trees = take n from curr_trees, whats left
        next_trees.append( Node(root, trees) )
    curr_trees = next_trees

curr_trees should be a list with the single root node now.

Я почти уверен, что теперь мы можем очень легко преобразовать это в одно присваивание Erlang / Haskell.