Difference between revisions of "Blow your mind"
DonStewart (talk  contribs) m (BlowYourMindIdioms moved to Blow your mind) 
(→Mathematical sequences, etc: comment tweak re complexity) 

(82 intermediate revisions by 33 users not shown)  
Line 1:  Line 1:  
Useful Idioms that will blow your mind (unless you already know them :) 
Useful Idioms that will blow your mind (unless you already know them :) 

−  This collection is supposed to be comprised of short, useful, cool, magical examples, which should incite the reader's curiosity and (hopefully) lead 
+  This collection is supposed to be comprised of short, useful, cool, magical examples, which should incite the reader's curiosity and (hopefully) lead to a deeper understanding of advanced Haskell concepts. At a later time I might add explanations to the more obscure solutions. I've also started providing several alternatives to give more insight into the interrelations of solutions. 
More examples are always welcome, especially "obscure" monadic ones. 
More examples are always welcome, especially "obscure" monadic ones. 

−  +  == List/String operations == 

−  <code> 

+  <haskell> 

 split at whitespace 
 split at whitespace 

 "hello world" > ["hello","world"] 
 "hello world" > ["hello","world"] 

words 
words 

−  +  unfoldr (\b > fmap (const . (second $ drop 1) . break (==' ') $ b) . listToMaybe $ b) 

+  
+  takeWhile (not . null) . evalState (repeatM $ modify (drop 1) 

+  >> State (break (== ' '))) . (' ' :) 

+  where repeatM = sequence . repeat 

fix (\f l > if null l then [] else let (s,e) = break (==' ') l in s:f (drop 1 e)) 
fix (\f l > if null l then [] else let (s,e) = break (==' ') l in s:f (drop 1 e)) 

−   splitting in two 
+   splitting in two alternating subsequences 
 "1234567" > ("1357", "246") 
 "1234567" > ("1357", "246") 

−  foldr (\a (x,y) > (a:y,x)) ([],[]) 

+   the lazy match with ~ is necessary for laziness, 

+   especially to enable processing of infinite lists 

+  foldr (\a ~(x,y) > (a:y,x)) ([],[]) 

(map snd *** map snd) . partition (even . fst) . zip [0..] 
(map snd *** map snd) . partition (even . fst) . zip [0..] 

−  transpose . unfoldr (\a > 
+  transpose . unfoldr (\a > toMaybe (not $ null a) (splitAt 2 a)) 
 this one uses the solution to the next problem in a nice way :) 
 this one uses the solution to the next problem in a nice way :) 

+  toMaybe b x = if b then Just x else Nothing 

+   or generalize it: 

+   toMaybe = (toMonadPlus :: Bool > a > Maybe a) 

+  toMonadPlus b x = guard b >> return x 

+   or with MonadComprehensions: [x  b] 

 splitting into lists of length N 
 splitting into lists of length N 

 "1234567" > ["12", "34", "56", "7"] 
 "1234567" > ["12", "34", "56", "7"] 

−  unfoldr (\a > 
+  unfoldr (\a > toMaybe (not $ null a) (splitAt 2 a)) 
takeWhile (not . null) . unfoldr (Just . splitAt 2) 
takeWhile (not . null) . unfoldr (Just . splitAt 2) 

+  
+  ensure :: MonadPlus m => (a > Bool) > a > m a 

+  ensure p x = guard (p x) >> return x 

+  unfoldr (ensure (not . null . fst) . splitAt 2) 

 sorting by a custom function 
 sorting by a custom function 

 length > ["abc", "ab", "a"] > ["a", "ab", "abc"] 
 length > ["abc", "ab", "a"] > ["a", "ab", "abc"] 

−  sortBy length 

+  comparing f = compare `on` f  "comparing" is already defined in Data.Ord 

+  sortBy (comparing length) 

−  map snd . sortBy fst . map (length &&& id) 
+  map snd . sortBy (comparing fst) . map (length &&& id) 
−   the so called "Schwartzian Transform" for computationally more expensive 
+   the so called "Schwartzian Transform" for computationally more expensive 
−  +   functions. 

+  
+   comparing adjacent elements 

+  rises xs = zipWith (<) xs (tail xs) 

 lazy substring search 
 lazy substring search 

 "ell" > "hello" > True 
 "ell" > "hello" > True 

−  substr a b = any (a ` 
+  substr a b = any (a `isPrefixOf`) $ tails b 
−  +  
+   multiple splitAt's: 

+   splitAts [2,5,0,3] [1..15] == [[1,2],[3,4,5,6,7],[],[8,9,10],[11,12,13,14,15]] 

+  splitAts = foldr (\n r > splitAt n >>> second r >>> uncurry (:)) return 

+  
+   frequency distribution 

+   "abracadabra" > fromList [('a',5),('b',2),('c',1),('d',1),('r',2)] 

+  import Data.Map 

+  histogram = fromListWith (+) . (`zip` repeat 1) 

+  
+   using arrows and sort 

+  histogramArr = map (head&&&length) . group . sort 

+   multidimensional zipWith 

+  zip2DWith :: (a > b > c) > [[a]] > [[b]] > [[c]] 

+  zip2DWith = zipWith . zipWith 

+  zip3DWith :: (a > b > c) > [[[a]]] > [[[b]]] > [[[c]]] 

+  zip3DWith = zipWith . zipWith . zipWith 

+   etc. 

+  </haskell> 

−  +  == Mathematical sequences, etc == 

−  <code> 

+  <haskell> 

−   factorial 
+   factorial 6 = 720 
−   6 > 720 

product [1..6] 
product [1..6] 

−  +  foldl' (*) 1 [1..6] 

−  (!!6) $ 
+  (!!6) $ scanl (*) 1 [1..] 
−  fix (\f n > if n <= 0 then 1 else n * f (n1)) 
+  fix (\f n > if n <= 0 then 1 else n * f (n1)) 6 
−   powers of two 
+   powers of two sequence 
−  iterate ( 
+  iterate (2*) 1 
−  +  fix ((1:) . map (2*)) 

+  unfoldr (\z > Just (z, 2*z)) 1 

−   fibonacci series 

−  unfoldr (\(f1,f2) > Just (f1,(f2,f1+f2))) (0,1) 

−  fibs = 0:1:zipWith (+) fibs (tail fibs) 

+   fibonacci sequence 

+  unfoldr (\(a,b) > Just (a,(b,a+b))) (0,1) 

−  +  fibs = 0 : 1 : zipWith (+) fibs (tail fibs) 

+  fib = 0 : scanl (+) 1 fib  also, fix ((0:) . scanl (+) 1) 

−   prime numbers 

+  
−   example of a memoising caf (??) 

+   pascal triangle 

+  pascal = iterate (\row > zipWith (+) ([0] ++ row) (row ++ [0])) [1] 

+  
+  
+   prime numbers 

primes = sieve [2..] where 
primes = sieve [2..] where 

−  sieve (p: 
+  sieve (p:xs) = p : sieve [ n  n < xs, n `mod` p > 0 ] 
unfoldr sieve [2..] where 
unfoldr sieve [2..] where 

−  sieve (p: 
+  sieve (p:xs) = Just(p, [ n  n < xs, n `mod` p > 0 ]) 
−  </code> 

+  otherPrimes = nubBy (((>1).).gcd) [2..] 

−  === Monad Magic === 

+   or if you want to use the Sieve of Eratosthenes 

+  diff xl@(x:xs) yl@(y:ys)  x < y = x:diff xs yl 

+   x > y = diff xl ys 

+   otherwise = diff xs ys 

−  <code> 

+  eprimes = sieve [2..] where 

+  sieve (p:xs) = p : sieve (diff xs [p, p+p..]) 

+   sieve (splitAt 1 > (h@(p:_),t)) = 

+   h ++ sieve (diff t [p, p+p..]) 

+  
+  fix $ map head . scanl diff [2..] . map (\p > [p, p+p..]) 

+  
+  
+   postponed to squares for under n^1.5 complexity 

+   instead of above n^2.0 

+  peprimes = 2 : sieve [[p*p, p*p+p..]  p < peprimes] [3..] where 

+  sieve ((q:cs):r) (span (< q) > (h,_:t)) = 

+  h ++ sieve r (diff t cs) 

+  
+   treefolded, ~n^1.2, w/ dataordlist's Data.List.Ordered.unionAll 

+  2 : _Y ((3:) . diff [5,7..] . unionAll . map (\p > [p*p, p*p+p..])) 

+  
+  _Y g = g (_Y g)  nonsharing recursion prevents memory retention 

+  
+  
+   Hamming numbers (`union`, `mergeAll` from dataordlist) 

+  h = 1 : foldr (\k > union (map (k*) h)) [] [2,3,5] 

+   or even just 

+  h = 1 : unionAll [map (k*) h  k < [2,3,5]] 

+  
+  foldr (\n > mergeAll . map (iterate (*n))) [1] [2,3,5] 

+  foldr (\n > mergeAll . iterate (map (*n))) [1] [2,3,5]  this too 

+  
+  h = 1 : foldr (\n s > fix (merge s . map (n*) . (1:))) [] [2,3,5] 

+   h = 1 : fix (merge s3 . map (2*) . (1:)) where 

+   s3 = fix (merge s5 . map (3*) . (1:))) where 

+   s5 = fix (map (5*) . (1:))) 

+  
+  merge a@(x:xs) b@(y:ys)  x < y = x : merge xs b  merge assumes 

+    x == y = x : union xs ys  there's no dups 

+   otherwise = y : merge a ys 

+  merge [] b = b  merge [] = \b > b = id  (id .) = id 

+  merge a [] = a 

+  
+  
+   enumerating the rationals (see [1]) 

+  rats :: [Rational] 

+  rats = iterate next 1 where 

+  next x = recip (fromInteger n+1y) where (n,y) = properFraction x 

+  
+   another way 

+  rats2 = fix ((1:) . (>>= \x > [1+x, 1/(1+x)])) :: [Rational] 

+  </haskell> 

+  
+  [1] [http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#rationals Gibbons, Lest, Bird  Enumerating the Rationals] 

+  
+  == Monad magic == 

+  
+  The list monad can be used for some amazing Prologish search problems. 

+  
+  <haskell> 

 all combinations of a list of lists. 
 all combinations of a list of lists. 

−   these solutions are all pretty much equivalent in that they run 
+   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"] 
 "12" > "45" > ["14", "15", "24", "25"] 

sequence ["12", "45"] 
sequence ["12", "45"] 

Line 100:  Line 183:  
do { x < "12"; y < "45"; return [x,y] } 
do { x < "12"; y < "45"; return [x,y] } 

−  "12" >>= \ 
+  "12" >>= \x > "45" >>= \y > return [x,y] 
−  
 all combinations of letters 
 all combinations of letters 

(inits . repeat) ['a'..'z'] >>= sequence 
(inits . repeat) ['a'..'z'] >>= sequence 

−  
 apply a list of functions to an argument 
 apply a list of functions to an argument 

 even > odd > 4 > [True,False] 
 even > odd > 4 > [True,False] 

Line 111:  Line 193:  
sequence [even,odd] 4 
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 
 apply a function to two other function the same argument 

Line 120:  Line 204:  
liftM2 (>>) putStrLn return "hello" 
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 
 forward function concatenation 

(*3) >>> (+1) $ 2 
(*3) >>> (+1) $ 2 

−  foldl1 (flip (.)) [( 
+  foldl1 (flip (.)) [(*3),(+1)] 2 
Line 134:  Line 221:  
 [still to categorize] 
 [still to categorize] 

−  ( 
+  ((+) =<< (+) =<< (+) =<< id) 3  (+) ((+) ((+) (id 3) 3) 3) 3 = 12 
+   might need to import Control.Monad.Instances 

−  (join . liftM2) (*) (+3) 5  64 

+   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`(ba)==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, ... 
mapAccumL (\acc n > (acc+n,acc+n)) 0 [1..10]  interesting for fac, fib, ... 

Line 143:  Line 256:  
do { Just x < [Nothing, Just 5, Nothing, Just 6, Just 7, Nothing]; return x } 
do { Just x < [Nothing, Just 5, Nothing, Just 6, Just 7, Nothing]; return x } 

−  </ 
+  </haskell> 
−  
−  +  == Other == 

−  <code> 

+  <haskell> 

 simulating lisp's cond 
 simulating lisp's cond 

case () of ()  1 > 2 > True 
case () of ()  1 > 2 > True 

Line 154:  Line 267:  
 otherwise > True 
 otherwise > True 

+  or: 

+  cond = foldr (uncurry if')  ' see [1] below 

 match a constructor 
 match a constructor 

−   this is better than applying all the arguments, because this way the 
+   this is better than applying all the arguments, because this way the 
+   data type can be changed without touching the code (ideally). 

case a of Just{} > True 
case a of Just{} > True 

_ > False 
_ > False 

+  
+  
+   spreadsheet magic 

+   might require import Control.Monad.Instances 

+  let loeb x = fmap ($ loeb x) x in 

+  loeb [ (!!5), const 3, liftM2 (+) (!!0) (!!1), (*2) . (!!2), length, const 17] 

Line 173:  Line 294:  
why functional fp matters (lazy search, ...) 
why functional fp matters (lazy search, ...) 

} 
} 

−  </ 
+  </haskell> 
+  
+  [1]: see [[Case]] and [[Ifthenelse]]. 

+  
+  === Polynomials === 

+  In abstract algebra you learn that polynomials can be used the same way integers are used given the right assumptions about their coefficients and roots. Specifically, polynomials support addition, subtraction, multiplication and sometimes division. It also turns out that one way to think of polynomials is that they are just lists of numbers (their coefficients). 

+  
+  instance Num a => Num [a] where  (1) 

+  
+  (f:fs) + (g:gs) = f+g : fs+gs  (2) 

+  fs + [] = fs  (3a) 

+  [] + gs = gs  (3b) 

+  
+  (f:fs) * (g:gs) = f*g : [f]*gs + fs*(g:gs)  (4) 

+  _ * _ = []  (5) 

+  
+  abs = undefined  I can't think of a sensible definition 

+  signum = map signum 

+  fromInteger n = [fromInteger n] 

+  negate = map (\x > x) 

+  
+  ====Explanation==== 

+  (1) puts lists into type class Num, the class to which operators + and * belong, provided the list elements are in class Num. 

+  
+  Lists are ordered by increasing powers. Thus <tt>f:fs</tt> means <tt>f+x*fs</tt> in algebraic notation. (2) and (4) follow from these algebraic identities: 

+  
+  (f+x*fs) + (g+x*gs) = f+g + x*(fs+gs) 

+  (f+x*fs) * (g+x*gs) = f*g + x*(f*gs + fs*(g+x*gs)) 

+  
+  (3) and (5) handle list ends. 

+  
+  The bracketed <tt>[f]</tt> in (4) avoids mixed arithmetic, which Haskell doesn't support. 

+  
+  ====Comments==== 

+  
+  The methods are qualitatively different from ordinary arraybased methods; there is no vestige of subscripting or counting of terms. 

+  
+  The methods are suitable for online computation. Only 

+  <i>n</i> terms of each input must be seen before the <i>n</i>th term 

+  of output is produced. 

+  
+  Thus the methods work on infinite series as well as polynomials. 

+  
+  Integer power comes for free. This example tests the cubing of (1+x): 

+  
+  [1, 1]^3 == [1, 3, 3, 1] 

+  
+  
+  This gives us the infinite list of rows of Pascal's triangle: 

+  
+  pascal = map ([1,1]^) [0..] 

+  
+  For example, 

+  
+  take 5 pascal  [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]] 

+  
+  See also 

+  * [[Pointfree]] 

+  * [https://hub.darcs.net/thielema/numericprelude/browse/src/MathObj/Polynomial.hs NumericPrelude: Polynomials] 

+  * [[Add polynomials]] 

+  * Solve differential equations in terms of [http://www.haskell.org/pipermail/haskellcafe/2004May/006192.html power series]. 

+  
+  [[Category:Idioms]] 

+  [[Category:Mathematics]] 
Latest revision as of 17:53, 22 November 2019
Useful Idioms that will blow your mind (unless you already know them :)
This collection is supposed to be comprised of short, useful, cool, magical examples, which should incite the reader's curiosity and (hopefully) lead to a deeper understanding of advanced Haskell concepts. At a later time I might add explanations to the more obscure solutions. I've also started providing several alternatives to give more insight into the interrelations of solutions.
More examples are always welcome, especially "obscure" monadic ones.
Contents
List/String operations
 split at whitespace
 "hello world" > ["hello","world"]
words
unfoldr (\b > fmap (const . (second $ drop 1) . break (==' ') $ b) . listToMaybe $ b)
takeWhile (not . null) . evalState (repeatM $ modify (drop 1)
>> State (break (== ' '))) . (' ' :)
where repeatM = sequence . repeat
fix (\f l > if null l then [] else let (s,e) = break (==' ') l in s:f (drop 1 e))
 splitting in two alternating subsequences
 "1234567" > ("1357", "246")
 the lazy match with ~ is necessary for laziness,
 especially to enable processing of infinite lists
foldr (\a ~(x,y) > (a:y,x)) ([],[])
(map snd *** map snd) . partition (even . fst) . zip [0..]
transpose . unfoldr (\a > toMaybe (not $ null a) (splitAt 2 a))
 this one uses the solution to the next problem in a nice way :)
toMaybe b x = if b then Just x else Nothing
 or generalize it:
 toMaybe = (toMonadPlus :: Bool > a > Maybe a)
toMonadPlus b x = guard b >> return x
 or with MonadComprehensions: [x  b]
 splitting into lists of length N
 "1234567" > ["12", "34", "56", "7"]
unfoldr (\a > toMaybe (not $ null a) (splitAt 2 a))
takeWhile (not . null) . unfoldr (Just . splitAt 2)
ensure :: MonadPlus m => (a > Bool) > a > m a
ensure p x = guard (p x) >> return x
unfoldr (ensure (not . null . fst) . splitAt 2)
 sorting by a custom function
 length > ["abc", "ab", "a"] > ["a", "ab", "abc"]
comparing f = compare `on` f  "comparing" is already defined in Data.Ord
sortBy (comparing length)
map snd . sortBy (comparing fst) . map (length &&& id)
 the so called "Schwartzian Transform" for computationally more expensive
 functions.
 comparing adjacent elements
rises xs = zipWith (<) xs (tail xs)
 lazy substring search
 "ell" > "hello" > True
substr a b = any (a `isPrefixOf`) $ tails b
 multiple splitAt's:
 splitAts [2,5,0,3] [1..15] == [[1,2],[3,4,5,6,7],[],[8,9,10],[11,12,13,14,15]]
splitAts = foldr (\n r > splitAt n >>> second r >>> uncurry (:)) return
 frequency distribution
 "abracadabra" > fromList [('a',5),('b',2),('c',1),('d',1),('r',2)]
import Data.Map
histogram = fromListWith (+) . (`zip` repeat 1)
 using arrows and sort
histogramArr = map (head&&&length) . group . sort
 multidimensional zipWith
zip2DWith :: (a > b > c) > [[a]] > [[b]] > [[c]]
zip2DWith = zipWith . zipWith
zip3DWith :: (a > b > c) > [[[a]]] > [[[b]]] > [[[c]]]
zip3DWith = zipWith . zipWith . zipWith
 etc.
Mathematical sequences, etc
 factorial 6 = 720
product [1..6]
foldl' (*) 1 [1..6]
(!!6) $ scanl (*) 1 [1..]
fix (\f n > if n <= 0 then 1 else n * f (n1)) 6
 powers of two sequence
iterate (2*) 1
fix ((1:) . map (2*))
unfoldr (\z > Just (z, 2*z)) 1
 fibonacci sequence
unfoldr (\(a,b) > Just (a,(b,a+b))) (0,1)
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fib = 0 : scanl (+) 1 fib  also, fix ((0:) . scanl (+) 1)
 pascal triangle
pascal = iterate (\row > zipWith (+) ([0] ++ row) (row ++ [0])) [1]
 prime numbers
primes = sieve [2..] where
sieve (p:xs) = p : sieve [ n  n < xs, n `mod` p > 0 ]
unfoldr sieve [2..] where
sieve (p:xs) = Just(p, [ n  n < xs, n `mod` p > 0 ])
otherPrimes = nubBy (((>1).).gcd) [2..]
 or if you want to use the Sieve of Eratosthenes
diff xl@(x:xs) yl@(y:ys)  x < y = x:diff xs yl
 x > y = diff xl ys
 otherwise = diff xs ys
eprimes = sieve [2..] where
sieve (p:xs) = p : sieve (diff xs [p, p+p..])
 sieve (splitAt 1 > (h@(p:_),t)) =
 h ++ sieve (diff t [p, p+p..])
fix $ map head . scanl diff [2..] . map (\p > [p, p+p..])
 postponed to squares for under n^1.5 complexity
 instead of above n^2.0
peprimes = 2 : sieve [[p*p, p*p+p..]  p < peprimes] [3..] where
sieve ((q:cs):r) (span (< q) > (h,_:t)) =
h ++ sieve r (diff t cs)
 treefolded, ~n^1.2, w/ dataordlist's Data.List.Ordered.unionAll
2 : _Y ((3:) . diff [5,7..] . unionAll . map (\p > [p*p, p*p+p..]))
_Y g = g (_Y g)  nonsharing recursion prevents memory retention
 Hamming numbers (`union`, `mergeAll` from dataordlist)
h = 1 : foldr (\k > union (map (k*) h)) [] [2,3,5]
 or even just
h = 1 : unionAll [map (k*) h  k < [2,3,5]]
foldr (\n > mergeAll . map (iterate (*n))) [1] [2,3,5]
foldr (\n > mergeAll . iterate (map (*n))) [1] [2,3,5]  this too
h = 1 : foldr (\n s > fix (merge s . map (n*) . (1:))) [] [2,3,5]
 h = 1 : fix (merge s3 . map (2*) . (1:)) where
 s3 = fix (merge s5 . map (3*) . (1:))) where
 s5 = fix (map (5*) . (1:)))
merge a@(x:xs) b@(y:ys)  x < y = x : merge xs b  merge assumes
  x == y = x : union xs ys  there's no dups
 otherwise = y : merge a ys
merge [] b = b  merge [] = \b > b = id  (id .) = id
merge a [] = a
 enumerating the rationals (see [1])
rats :: [Rational]
rats = iterate next 1 where
next x = recip (fromInteger n+1y) where (n,y) = properFraction x
 another way
rats2 = fix ((1:) . (>>= \x > [1+x, 1/(1+x)])) :: [Rational]
[1] Gibbons, Lest, Bird  Enumerating the Rationals
Monad magic
The list monad can be used for some amazing Prologish search problems.
 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`(ba)==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 }
Other
 simulating lisp's cond
case () of ()  1 > 2 > True
 3 < 4 > False
 otherwise > True
or:
cond = foldr (uncurry if')  ' see [1] below
 match a constructor
 this is better than applying all the arguments, because this way the
 data type can be changed without touching the code (ideally).
case a of Just{} > True
_ > False
 spreadsheet magic
 might require import Control.Monad.Instances
let loeb x = fmap ($ loeb x) x in
loeb [ (!!5), const 3, liftM2 (+) (!!0) (!!1), (*2) . (!!2), length, const 17]
{
TODO, IDEAS:
more fun with monad, monadPlus (liftM, ap, guard, when)
fun with arrows (second, first, &&&, ***)
liftM, ap
lazy search (searching as traversal of lazy structures)
innovative data types (i.e. having fun with Maybe sequencing)
LINKS:
bananas, envelopes, ... (generic traversal)
why functional fp matters (lazy search, ...)
}
[1]: see Case and Ifthenelse.
Polynomials
In abstract algebra you learn that polynomials can be used the same way integers are used given the right assumptions about their coefficients and roots. Specifically, polynomials support addition, subtraction, multiplication and sometimes division. It also turns out that one way to think of polynomials is that they are just lists of numbers (their coefficients).
instance Num a => Num [a] where  (1)
(f:fs) + (g:gs) = f+g : fs+gs  (2) fs + [] = fs  (3a) [] + gs = gs  (3b)
(f:fs) * (g:gs) = f*g : [f]*gs + fs*(g:gs)  (4) _ * _ = []  (5)
abs = undefined  I can't think of a sensible definition signum = map signum fromInteger n = [fromInteger n] negate = map (\x > x)
Explanation
(1) puts lists into type class Num, the class to which operators + and * belong, provided the list elements are in class Num.
Lists are ordered by increasing powers. Thus f:fs means f+x*fs in algebraic notation. (2) and (4) follow from these algebraic identities:
(f+x*fs) + (g+x*gs) = f+g + x*(fs+gs) (f+x*fs) * (g+x*gs) = f*g + x*(f*gs + fs*(g+x*gs))
(3) and (5) handle list ends.
The bracketed [f] in (4) avoids mixed arithmetic, which Haskell doesn't support.
Comments
The methods are qualitatively different from ordinary arraybased methods; there is no vestige of subscripting or counting of terms.
The methods are suitable for online computation. Only n terms of each input must be seen before the nth term of output is produced.
Thus the methods work on infinite series as well as polynomials.
Integer power comes for free. This example tests the cubing of (1+x):
[1, 1]^3 == [1, 3, 3, 1]
This gives us the infinite list of rows of Pascal's triangle:
pascal = map ([1,1]^) [0..]
For example,
take 5 pascal  [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]
See also
 Pointfree
 NumericPrelude: Polynomials
 Add polynomials
 Solve differential equations in terms of power series.