[WARNING: braindamag(ed|ing) experience following] Hi all, a few days ago I decided I desperately needed a set which could contain (among others) itself. My first idea was
module Main where
import List import Monad
data Elem s a = V a | R (s (Elem s a))
Now, a self-containing list can be defined as
l :: [Elem [] Integer] l = [V 42, R [V 6, V 7], R l]
As my brain could handle that, and I noticed quite some similiarity between Elem and Either, I decided to try to abstract the thing a little. This is what I ultimately came up with
newtype Comp f g x = Comp (f (g x)) newtype Rec f = In (f (Rec f))
The idea is that `Elem s a' is basically just `Either a (s SELF)'. Then, instead of defining a special-purpose mutually-recursive "fixed-point type", another type `Comp' is defined to compose two types into one, to enable the standard Fix/Mu/Rec type to be used.
type RecCont s a= s (Either a (RecElem s a))
A recursive container is a container with simple elements (Left a) and recursive container-elements (Right (RecElem s a))
type RecElem s a= Rec (Comp s (Either a))
And a recursive container-element is, err, a slightly obscured recursive container. (s (Either a SELF))
el :: a -> Either a (RecElem s a) el = Left
rec :: RecCont s a -> Either a (RecElem s a) rec = Right . In . Comp
unRec :: RecElem s a -> RecCont s a unRec (In (Comp f)) = f
And indeed, a list (or set, or whatever) which contains itself is easily defined.
s :: RecCont [] Integer s = [el 42, rec [el 6, el 7], rec s]
The next step was to try to get it an instance of Show. Funny enough, around that time, Shin-Cheng Mu posed the question of how to make Rec an instance of Show[1], the (Haskell98) solution of which I had just found on the HaWiki.[2]
class RecShow f where recShow :: Show a => f a -> String
instance RecShow f => Show (Rec f) where show (In f) = "(In (" ++ recShow f ++ "))"
instance Show a => RecShow (Either a) where recShow = show
However, I didn't just want some `Rec f' to be an instance of Show, I wanted `Rec (Comp f g)' to be an instance of Show. Which turned out not to be all that easy. My best solution works, but I hope someone has a better idea...?
class CompShow f where compShow :: (Show a, RecShow g) => f (g a) -> String
instance (CompShow f, RecShow g, Show a) => Show (Comp f g a) where show (Comp f)= "(Comp (" ++ compShow f ++ "))"
instance CompShow [] where compShow l = "[" ++ (concat $ intersperse "," $ map recShow l) ++ "]"
instance (CompShow f, RecShow g) => RecShow (Comp f g) where recShow = show
Anyway, once this worked I just had to find some use for it ;)
flatten :: (Monad s, Functor s) => RecCont s a -> s a flatten = join . fmap (either return (flatten . unRec))
noI'mNotEvil :: Num a => a -> RecCont IO a noI'mNotEvil n = do putStrLn $ showString "Attempt #" $ shows n $ ": Hi, what's The Answer?" s <- getLine return $ if s == "42" then el n else rec (noI'mNotEvil (n+1))
main = do n <- flatten (noI'mNotEvil 1) if n > 1 then putStrLn "Did that really have to take so long?" else putStrLn "Well done!"
[1] http://www.haskell.org//pipermail/haskell/2005-February/015325.html [2] http://www.haskell.org/hawiki/PreludeExts -- Nobody can be exactly like me. Even I have trouble doing it.