How can I dynamically allocate cyclic data?

Question

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 simplest automaton:

sink =
  Auto sink sink

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
otto1 =
  Auto otto1 sink

-- Mutually recursive automata
otto2 =
  Auto otto2 otto3

otto3 =
  Auto otto3 otto2

These are nice. But it might be nice to 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. Our previous examples which were O(1) to follow a transition. However 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 kept 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 automata built dynamically with the method to be just as performant as ones built statically like the ones shown earlier. I'd like some way to analyze the input, construct an automaton and then free the input up up.

In a language with mutation this is easy to do 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?

Magnanimity

Pedantic note: as-is, your Automaton type is not very useful since there is no way to distinguish one value from another. So, fromTransition _ = let a = Auto a a in a would technically be a correct answer. Of course, adding some field to Automaton, say an Int, makes the problem no longer trivial. – Parvenu

Answer 1

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

Persevere

You can reduce building time by converting the transition matrix to IntMap (Int, Int) using fromDistinctAscList (zip [0..] m) and then just fmapping over it to make a. Now lookups are logarithmic time and fast. – Pyrites

For that matter, you could do the same with an array! Anything but a list. – Pyrites

I believe this is sometimes called “tying the knot”; that is a good term to search if one wants more information about this method. – Estrade

shouldn't fromTransition ((0,0):undefined) work though? also ... ((0,1),(1,0):undefined) ; a.o.t. ... ((0,1),(1,2):undefined). – Cloy

I don't think that should necessarily work, but if you wanted to you would have to find a smarter way to force only the elements you need. – Persevere

I couldn't find it in the five to ten minutes I spent on it. hoped you would... :) what I had was fromTransition m = aforce (a !! 0) where { a = map (\(s,f) -> Auto (a !! s) (a !! f)) m } but then aforce, couldn't come up with the proper way to define it that would work in all the needed cases. ((0,0):undefined) worked, but the others would cause a stack overflow or with other definitions they would succeed where they shouldn't, like with ((0,1),(1,2):undefined). – Cloy

It's going to be a DFS, and the logic to avoid cycles and duplicate work can be a bit tricky. – Persevere

I was hoping for some trick from the libraries that would get us the normal form by itself, like deepseq. – Cloy