Что такое «путь Haskell» для транспонирования графика?

Question

Предположим, что у меня есть дерево, представленное как список родителей, и я хочу повернуть ребрами, получив список дочерних элементов для каждого узла. Для этого дерева - http://i.stack.imgur.com/uapqT.png - преобразование будет выглядеть следующим образом:

[0,0,0,1,1,2,5,4,4] -> [[2,1],[4,3],[5],[],[8,7],[6],[],[],[]] 

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

По существу, мой вопрос: «Что такое идиоматический способ Хаскелла разрешить такие вещи?». Насколько я понимаю, я могу сделать это императивно с помощью изменчивых векторов, но разве нет какого-то чисто функционального метода? Если нет, то как правильно использовать mutables?

И, наконец, мне нужно, чтобы он работал быстро, то есть O (n) сложность и нестандартные пакеты для меня не являются опцией.

Answer 1

Стоит рассмотреть чистые функции в Data.Vector или Data.Array, которые внутренне используют мутацию, для того, чтобы быть более эффективным (в accum -s в обеих библиотеках, плюс разворачиваясь и construct -s в vector).

accum -s отлично, когда мы не заботимся о промежуточных состояниях массива во время строительства. Они хорошо применимы для транспонирования графиков, хотя мы должны обеспечить диапазон для ключей узлов:

{-# LANGUAGE TupleSections #-} 

import qualified Data.Array as A 

type Graph = [(Int, [Int])] 

transpose :: (Int, Int) -> Graph -> Graph 
transpose range g = 
    A.assocs $ A.accumArray (flip (:)) [] range (do {(i, ns) <- g; map (,i) ns}) 

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

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

К счастью, IntMap предоставляет множество функций более высокого порядка, поэтому мы не всегда (всегда) вынуждены программировать в императивном стиле с ним. Существует аналог для accum, например:

import qualified Data.IntMap.Strict as IM 

transpose :: Graph -> Graph 
transpose g = 
    IM.assocs $ IM.fromListWith (++) (do {(i, ns) <- g; (i,[]) : map (,[i]) ns}) 

Answer 2

Чисто функциональный способ будет использовать карту для хранения информации, производя O (п журнал п) алгоритм:

import qualified Data.IntMap as IM 
import Data.Maybe (fromMaybe) 

childrenMap :: [Int] -> IM.IntMap [Int] 
childrenMap xs = foldr addChild IM.empty $ zip xs [0..] 
    where 
    addChild :: (Int, Int) -> IM.IntMap [Int] -> IM.IntMap [Int] 
    addChild (parent, child) = IM.alter (Just . (child :) . fromMaybe []) parent 

Вы также можете использовать императивное решение и сохранить вещи чистые, используя ST monad, что, очевидно, о (п), но императив код несколько затемняет основную идею:

import Control.Monad (forM_) 
import Data.Array 
import Data.Array.MArray 
import Data.Array.ST 

childrenST :: [Int] -> [[Int]] 
childrenST xs = elems $ runSTArray $ do 
    let l = length xs 
    arr <- newArray (0, l - 1) [] 
    let add (parent, child) = 
      writeArray arr parent . (child :) =<< readArray arr parent 
    forM_ (zip xs [0..]) add 
    return arr 

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