In addition to Telastyn's answer:
Maybe
never "silently fails". In contrast to null, which might be what the OP's is comparing it to, a Haskell function which can return Nothing
must explicitly do so in its type.
For comparison: a method returning String
in Java might return a String or null, and you cannot tell just by looking at its type:
public String myFunc(int x) { /* do something, might return null! */ }
In Haskell a function which returns a String
has a type similar to this:
myFunc :: Int -> String
You know it cannot return Nothing
, because if it did, its type would be:
myFunc :: Int -> Maybe String
This means Nothing
can never sneak up on you and "cause headaches down the line"!
You can expand your matrix grammar into an ADT with perfect sharing with a little bit of trickery:
{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}
import Data.Map
import Data.Foldable
import Data.Functor
import Data.Traversable
-- | Type synonym for non-terminal symbols
type NonTerminal = String
-- | Data type for the right hand side of a production
data RHS a = DownStep NonTerminal NonTerminal NonTerminal NonTerminal | Terminal a
deriving (Eq,Ord,Show,Read,Functor, Foldable, Traversable)
data G a = G NonTerminal (Map NonTerminal (RHS a))
deriving (Eq,Ord,Show,Read,Functor)
data M a = Q (M a) (M a) (M a) (M a) | T a
deriving (Functor, Foldable, Traversable)
tabulate :: G a -> M a
tabulate (G s pm) = loeb (expand <$> pm) ! s where
expand (DownStep a11 a12 a21 a22) m = Q (m!a11) (m!a12) (m!a21) (m!a22)
expand (Terminal a) _ = T a
loeb :: Functor f => f (f b -> b) -> f b
loeb x = xs where xs = fmap ($xs) x
Here I generalized your grammars to allow for any data type, not just Int, and tabulate
will take the grammar and expand it by folding it in upon itself using loeb
.
loeb
is described in an article by Dan Piponi
The resulting expansion as an ADT physically takes no more memory than the original grammar -- in fact it takes a fair bit less, because it doesn't need the extra log-factor for the Map spine, and it doesn't need to store the strings at all.
Unlike the naive expansion, using loeb
lets me 'tie the knot' and share the thunks for all occurrences of the same non-terminal.
If you want to dip more into the theory of all of this, we can see that RHS
could be turned into a base functor:
data RHS t nt = Q nt nt nt nt | L t
and then my M type is just the fixed point of that Functor
.
M a ~ Mu (RHS a)
while G a
would consist of a chosen string and a map from strings to (RHS String a)
.
We can then expand G
into M
by lookup up the entry in a map of expanded strings lazily.
This is sort of the dual of what is done in the data-reify
package, which can take such a base functor, and something like M
and recover the moral equivalent of your G
from it. They use a different type for the non-terminal names, which is basically just an Int
.
data Graph e = Graph [(Unique, e Unique)] Unique
and provide a combinator
reifyGraph :: MuRef s => s -> IO (Graph (DeRef s))
which can be used with an appropriate instance on the above data types to get a graph (MatrixGrammar) out of an arbitrary matrix. It won't do deduplication of identical but separately stored quadrants, but it'll recover all of the sharing that is present in the original graph.
Best Answer
According to A History of Haskell: Being Lazy With Class (see section 7) three different models were considered initially: streams, continuations and "world passing" (I don't know much about Clean, but it sounds like this is the Clean way?).
The last paragraph of section 7.2 indicates that the uniqueness type concept wasn't developed at this time:
The concept of monads seems to have been introduced (reused from other work) in later revisions of Haskell since it resulted in cleaner code (compared to continuations/streams):