How can I dynamically allocate cyclic data?-CodePudding

For the sake of example let's define a toy automaton type:

data Automaton =
  Auto
    { success ::
      Automaton
    , failure ::
      Automaton
    }

This structure is designed to by cyclic, we can imagine each Automaton as a state with success and failure transitions to other states. So finite automata must be defined recursively. For example here is the simplet automaton

otto1 =
  Auto otto1 otto1

It consists of 1 state that always transitions to itself. If we want we can make more complex automata:

-- Transitions to a sink once it encounters a failure
otto2 =
  Auto otto2 otto1

-- Mutually recursive automata
otto3 =
  Auto otto3 otto4

otto4 =
  Auto otto4 otto3

These are nice, but it might be nice to for example take user input and construct an automaton. For example maybe build one out of a transition matrix. Here's a naive implementation:

fromTransition :: [(Int, Int)] -> Automaton
fromTransition tMatrix =
  go 0
  where
    go n =
      let
        (succ, fail) =
          tMatrix !! n
      in
        Auto (go succ) (go fail)

However when we try to do this there starts to be an issue. Unlike our previous examples which were O(1) to follow a transition automata produced by this are O(n) to follow a transition, since barring caching, a list must be indexed every time we make a transition. In addition the input list must be held onto in memory as long as this automaton is. Making this basically just worse than using the transition matrix as the automaton.

What I'd really like is some way to analyze the input and construct an automaton and then free that up. I'd like automata built dynamically with the method to be just as performant as ones built statically like the ones shown earlier.

In a language with mutation it's easy to do this because we can create the structure bit by bit leaving holes behind to correct later.

I'd also really like to not drag the IO in because once introduced it can't be contained.

Is there a nice way to allocate cyclic structures dynamically like I want?

CodePudding user response：

Laziness to the rescue. We can recursively define a list of all the sub-automata, such that their transitions index into that same list:

fromTransition :: [(Int, Int)] -> Automaton
fromTransition m = a !! 0 where
  a = map (\(succ,fail) -> Auto (a !! succ) (a !! fail)) m

After all the transitions have been traversed at least once, the resulting automaton will be the cyclic graph you expect, without any reference to the matrix (and in particular, transitions will be taken in constant time).

We can also force the automaton ahead of time using seq.

fromTransition :: [(Int, Int)] -> Automaton
fromTransition m = forced `seq` (a !! 0) where
  a = map (\(succ,fail) -> Auto (a !! succ) (a !! fail)) m
  forced = foldr (\(Auto x y) r -> x `seq` y `seq` r) () a