Skip to content

Instantly share code, notes, and snippets.

@cbarrett
Last active August 29, 2015 13:58
Show Gist options
  • Save cbarrett/9928956 to your computer and use it in GitHub Desktop.
Save cbarrett/9928956 to your computer and use it in GitHub Desktop.
SICP's amb is the list monad, by example
-- You can find the original in section 4.3.2 of SICP: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#%_sec_4.3.2
import Data.List
distinct :: Eq a => [a] -> Bool
distinct xs = length (nub xs) == length xs
require :: Bool -> [[a]] -> [[a]]
require b e = if b then e else return []
data Name = Baker | Cooper | Fletcher | Miller | Smith
deriving (Show, Eq)
multipleDwelling :: [[(Name, Int)]]
multipleDwelling = filter (not . null) $ do
baker <- [1, 2, 3, 4, 5]
cooper <- [1, 2, 3, 4, 5]
fletcher <- [1, 2, 3, 4, 5]
miller <- [1, 2, 3, 4, 5]
smith <- [1, 2, 3, 4, 5]
require (distinct [baker, cooper, fletcher, miller, smith]) $
require (not (baker == 5)) $
require (not (cooper == 1)) $
require (not (fletcher == 5)) $
require (not (fletcher == 1)) $
require (miller > cooper) $
require (not (abs (smith - fletcher) == 1)) $
require (not (abs (fletcher - cooper) == 1)) $
return [ (Baker, baker)
, (Cooper, cooper)
, (Fletcher, fletcher)
, (Miller, miller)
, (Smith, smith)
]
-- And indeed, when we run this, we get:
-- *Main> multipleDwelling
-- [[(Baker,3),(Cooper,2),(Fletcher,4),(Miller,5),(Smith,1)]]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment