Acyclic Examples

AcyclicMoand.hs

module AcyclicMonad (dag, singleton, edgeTo) where
-- Only export dag, singleton and edgeTo.

import Control.Monad.Trans.State.Strict

type Vertex = Int

newtype DAG = DAG DAG' deriving Show

-- eg. Edges 4 [2, 3] (Edges 3 [1] (Edges 2 [1] (Edges 1 [] Nil)))
-- represents 4 * 2 + 4 * 3 + 3 * 1 + 2 * 1 + 1
data DAG'
  = Cons Vertex
         [DAG']
         DAG'
  | Nil
  deriving (Show)

-- A simple helper function
vertex (Cons i _ _) = i
vertex Nil = 0

-- A State monad creating a singleton
singleton = modify (\s -> Cons (1 + vertex s) [] s) >> get

-- A State monad resulting in proper edges
edgeTo es = modify (\s -> Cons (1 + vertex s) es s) >> get

-- A simple function to run the state to get DAG in return
dag = DAG . snd . flip runState Nil

-- The result : DAG 3 [1..DAG,2..DAG] (DAG 2 [] (DAG 1 [] Nil))
dagTest =
  dag $ do
    v1 <- singleton
    v2 <- singleton
    edgeTo [v1, v2]

@anfelor

data Acyclic n a = Acyclic (AdjacencyMap a) (Vector n a)

Could you please give me a simple example?

I think one can go a step further and eliminate the "dag monad" completely? (But I don't think it's worth it.)
I try a few experiments and get back to you!