Editing Blow your mind (section)

== Monad magic ==

The list monad can be used for some amazing Prolog-ish search problems.

<haskell>
  -- all combinations of a list of lists.
  -- these solutions are all pretty much equivalent in that they run
  -- in the List Monad. the "sequence" solution has the advantage of
  -- scaling to N sublists.
  -- "12" -> "45" -> ["14", "15", "24", "25"]
  sequence ["12", "45"]

  [[x,y] | x <- "12", y <- "45"]

  do { x <- "12"; y <- "45"; return [x,y] }

  "12" >>= \x -> "45" >>= \y -> return [x,y]

  -- all combinations of letters
  (inits . repeat) ['a'..'z'] >>= sequence

  -- apply a list of functions to an argument
  -- even -> odd -> 4 -> [True,False]
  map ($4) [even,odd]

  sequence [even,odd] 4

  -- all subsequences of a sequence/ aka powerset.
  filterM (const [True, False])

  -- apply a function to two other function the same argument
  --   (lifting to the Function Monad (->))
  -- even 4 && odd 4 -> False
  liftM2 (&&) even odd 4

  liftM2 (>>) putStrLn return "hello"

  -- enumerate all rational numbers
  fix ((1%1 :) . (>>= \x -> [x+1, 1/(x+1)]))
  [1%1,2%1,1%2,3%1,1%3,3%2,2%3,4%1,1%4,4%3,3%4,5%2,2%5,5%3,3%5,5%1,1%5,5%4,4%5...
  
  -- forward function concatenation
  (*3) >>> (+1) $ 2

  foldl1 (flip (.)) [(*3),(+1)] 2


  -- perform functions in/on a monad, lifting
  fmap (+2) (Just 2)

  liftM2 (+) (Just 4) (Just 2)


  -- [still to categorize]
  ((+) =<< (+) =<< (+) =<< id) 3        -- (+) ((+) ((+) (id 3) 3) 3) 3 = 12
                               -- might need to import Control.Monad.Instances

  -- Galloping horsemen
  -- A large circular track has only one place where horsemen can pass;
  -- many can pass at once there.  Is it possible for nine horsemen to
  -- gallop around it continuously, all at different constant speeds?
  -- the following prints out possible speeds for 2 or more horsemen.
  spd s = ' ': show s ++ '/': show (s+1)
  ext (c,l) = [(tails.filter(\b->a*(a+1)`mod`(b-a)==0)$r,a:l) | (a:r)<-c]
  put = putStrLn . ('1':) . concatMap spd . reverse . snd . head
  main = mapM_ put . iterate (>>= ext) $ [(map reverse $ inits [1..],[])]

  -- output:
  1 1/2
  1 2/3 1/2
  1 3/4 2/3 1/2
  1 5/6 4/5 3/4 2/3
  1 12/13 11/12 10/11 9/10 8/9
  1 27/28 26/27 25/26 24/25 23/24 20/21
  1 63/64 60/61 59/60 57/58 56/57 55/56 54/55
  1 755/756 741/742 740/741 735/736 734/735 728/729 727/728 720/721
  1 126224/126225 122759/122760 122549/122550 122528/122529 122451/122452
    122444/122445 122374/122375 122304/122305 122264/122265


  double = join (+)                     -- double x = x + x

  (join . liftM2) (*) (+3) 5            -- (5+3)*(5+3) = 64
                               -- might need to import Control.Monad.Instances

  mapAccumL (\acc n -> (acc+n,acc+n)) 0 [1..10] -- interesting for fac, fib, ...

  do f <- [not, not]; d <- [True, False]; return (f d) -- [False,True,False,True]

  do { Just x <- [Nothing, Just 5, Nothing, Just 6, Just 7, Nothing]; return x }
</haskell>