How to enumerate a recursive datatype in Haskell?

by

My first ugly approach was:

allTerms :: Omega T
allTerms = do
  which <- each [ 1,2,3 ]
  if which == 1 then
    return A
  else if which == 2 then do
    x <- allTerms
    return $ B x
  else do
    x <- allTerms
    y <- allTerms
    return $ C x y

But then, after some cleaning up I reached this one liner

import Control.Applicative
import Control.Monad.Omega
import Control.Monad

allTerms :: Omega T
allTerms = join $ each [return A, B <$> allTerms, C <$> allTerms <*> allTerms]

Note that order matters: return A has to be the first choice in the list above, or allTerms will not terminate. Basically, the Omega monad ensures a “fair scheduling” among choices, saving you from e.g. infiniteList ++ something, but does not prevent infinite recursion.

An even more elegant solution was suggested by Crazy FIZRUK, exploiting the
Alternative instance of Omega.

import Control.Applicative
import Data.Foldable (asum)
import Control.Monad.Omega

allTerms :: Omega T
allTerms = asum [ pure A
                , B <$> allTerms
                , C <$> allTerms <*> allTerms
                ]

More Related Contents:

  1. What is a monad?
  2. Applicatives compose, monads don’t
  3. Is monad bind (>>=) operator closer to function composition (chaining) or function application?
  4. Large-scale design in Haskell? [closed]
  5. Is Haskell truly pure (is any language that deals with input and output outside the system)?
  6. Should do-notation be avoided in Haskell?
  7. What is a monad?
  8. How to use (->) instances of Monad and confusion about (->)
  9. Why are side-effects modeled as monads in Haskell?
  10. How to interpret bind/>>= of the function instance?
  11. How Monads are considered pure?
  12. Getting started with Haskell
  13. What does (f .) . g mean in Haskell?
  14. What are paramorphisms?
  15. How do functors work in haskell?
  16. Euler 43 – is there a monad to help write this list comprehension?
  17. Why does haskell’s bind function take a function from non-monadic to monadic
  18. Difference between Monad and Applicative in Haskell
  19. Why is lazy evaluation useful?
  20. Is there a way to place some impure code inside pure functions?
  21. How to increment a variable in functional programming?
  22. What are free monads?
  23. What part of Hindley-Milner do you not understand?
  24. Iterate over all pair combinations without repetition in Haskell
  25. Is there a monad that doesn’t have a corresponding monad transformer (except IO)?
  26. What does “pure” mean in “pure functional language”?
  27. How to return a pure value from a impure method
  28. Functional lenses
  29. Why does OCaml sometimes require eta expansion?
  30. Explanation of “tying the knot”

Leave a Comment