Personal tools

Blow your mind

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(more links on polynomials)
m (Mathematical sequences, etc)
 
(43 intermediate revisions by 24 users not shown)
Line 6: Line 6:
   
   
== List/String Operations ==
+
== List/String operations ==
   
   
Line 14: Line 14:
 
words
 
words
   
takeWhile (not . null) . unfoldr (Just . (second $ drop 1) . break (==' '))
+
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))
Line 21: Line 21:
 
-- splitting in two (alternating)
 
-- splitting in two (alternating)
 
-- "1234567" -> ("1357", "246")
 
-- "1234567" -> ("1357", "246")
foldr (\a (x,y) -> (a:y,x)) ([],[])
+
-- the lazy match with ~ is necessary for efficiency, especially enabling
  +
-- 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 -> if null a then Nothing else Just $ splitAt 2 a)
+
transpose . unfoldr (\a -> toMaybe (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
   
 
-- splitting into lists of length N
 
-- splitting into lists of length N
 
-- "1234567" -> ["12", "34", "56", "7"]
 
-- "1234567" -> ["12", "34", "56", "7"]
unfoldr (\a -> if null a then Nothing else Just $ splitAt 2 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"]
comparing f x y = compare (f x) (f y)
+
comparing f = compare `on` f -- "comparing" is already defined in Data.Ord
 
sortBy (comparing length)
 
sortBy (comparing length)
   
Line 46: Line 54:
   
 
-- comparing adjacent elements
 
-- comparing adjacent elements
rises xs = zipWith (<) xs (drop 1 xs)
+
rises xs = zipWith (<) xs (tail xs)
 
 
 
-- lazy substring search
 
-- lazy substring search
Line 55: Line 63:
 
-- splitAts [2,5,0,3] [1..15] == [[1,2],[3,4,5,6,7],[],[8,9,10],[11,12,13,14,15]]
 
-- 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
 
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>
 
</haskell>
   
== Mathematical Sequences, etc ==
+
== Mathematical sequences, etc ==
   
   
Line 65: Line 88:
 
product [1..6]
 
product [1..6]
   
foldl1 (*) [1..6]
+
foldl1 (*) [1..6] -- this won't work for 0; use "foldl (*) 1 [1..n]" instead
   
 
(!!6) $ scanl (*) 1 [1..]
 
(!!6) $ scanl (*) 1 [1..]
Line 83: Line 106:
 
fibs = 0:1:zipWith (+) fibs (tail fibs)
 
fibs = 0:1:zipWith (+) fibs (tail fibs)
   
fib = 0:scanl (+) 1 fib
+
fib = 0:scanl (+) 1 fib -- also seen as: fibs = fix ((0:) . scanl (+) 1)
   
   
Line 93: Line 116:
 
-- example of a memoising caf (??)
 
-- example of a memoising caf (??)
 
primes = sieve [2..] where
 
primes = sieve [2..] where
sieve (p:x) = p : sieve [ n | n <- x, n `mod` p > 0 ]
+
sieve (p:xs) = p : sieve [ n | n <- xs, n `mod` p > 0 ]
   
 
unfoldr sieve [2..] where
 
unfoldr sieve [2..] where
sieve (p:x) = Just(p, [ n | n <- x, n `mod` p > 0 ])
+
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..
 
-- or if you want to use the Sieve of Eratosthenes..
diff [] l = l
 
diff l [] = l
 
 
diff xl@(x:xs) yl@(y:ys) | x < y = x:diff xs yl
 
diff xl@(x:xs) yl@(y:ys) | x < y = x:diff xs yl
| x > y = diff xl ys
+
| x > y = diff xl ys
| otherwise = diff xs ys
+
| otherwise = diff xs ys
esieve [] = []
+
eprimes = esieve [2..] where
esieve (p:ps) = p:esieve (diff ps (iterate (+p) p))
+
esieve (p:xs) = p : esieve (diff xs [p, p+p..])
eprimes = esieve [2..]
+
  +
-- or if you want your n primes in less than n^1.5 time instead of n^2.2+
  +
peprimes = 2 : pesieve [3..] peprimes 4 where
  +
pesieve xs (p:ps) q | (h,t) <- span (<q) xs
  +
= h ++ pesieve (diff t [q, q+p..]) ps (head ps^2)
   
 
-- enumerating the rationals (see [1])
 
-- enumerating the rationals (see [1])
Line 112: Line 133:
 
rats = iterate next 1 where
 
rats = iterate next 1 where
 
next x = recip (fromInteger n+1-y) where (n,y) = properFraction x
 
next x = recip (fromInteger n+1-y) where (n,y) = properFraction x
  +
  +
-- another way
  +
rats2 = fix ((1:) . (>>= \x -> [1+x, 1/(1+x)])) :: [Rational]
 
</haskell>
 
</haskell>
   
 
[1] [http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#rationals Gibbons, Lest, Bird - Enumerating the Rationals]
 
[1] [http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#rationals Gibbons, Lest, Bird - Enumerating the Rationals]
   
== Monad Magic ==
+
== Monad magic ==
   
  +
The list monad can be used for some amazing Prolog-ish search problems.
   
 
<haskell>
 
<haskell>
Line 132: Line 157:
   
 
"12" >>= \a -> "45" >>= \b -> return [a,b]
 
"12" >>= \a -> "45" >>= \b -> return [a,b]
 
   
 
-- 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 143: Line 166:
   
 
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 152: Line 175:
 
liftM2 (>>) putStrLn return "hello"
 
liftM2 (>>) putStrLn return "hello"
   
  +
fix ((1:) . (>>= \x -> [x+1, 1/(x+1)])) :: [Rational]
  +
[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
Line 166: Line 191:
   
 
-- [still to categorize]
 
-- [still to categorize]
(id >>= (+) >>= (+) >>= (+)) 3 -- (3+3)+(3+3) = 12
+
(id >>= (+) >>= (+) >>= (+)) 3 -- 3+3+3+3 = 12
  +
-- Note: 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`(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 (+)
  +
  +
(join . liftM2) (*) (+3) 5 -- (5+3)*(5+3) = 64
  +
-- Note: 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 176: Line 201:
 
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>
 
</haskell>
 
   
 
== Other ==
 
== Other ==
Line 187: Line 211:
 
| otherwise -> True
 
| otherwise -> True
   
  +
--or:
  +
cond = foldr (uncurry if') -- see [1] below
   
 
-- match a constructor
 
-- match a constructor
Line 193: Line 219:
 
case a of Just{} -> True
 
case a of Just{} -> True
 
_ -> False
 
_ -> False
  +
  +
  +
-- spreadsheet magic
  +
-- requires 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 208: Line 240:
 
-}
 
-}
 
</haskell>
 
</haskell>
  +
  +
[1]: see [[Case]] and [[If-then-else]].
   
 
=== Polynomials ===
 
=== 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). Here is one way to use lists to model polynomials. Since polynomials can support the same operations as integers, we model polynomials by making a list of numbers an instance of the Num type class.
+
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).
   
<haskell>
+
instance Num a => Num [a] where -- (1)
-- First we tell Haskell that we want to make lists (or [a]) an instance of Num.
 
-- We refer to this instance of the Num type class as Num [a].
 
-- If you tried to use just:
 
-- "instance Num [a] where"
 
-- You'd get errors because the element type a is too general, too unconstrainted
 
-- for what we need.
 
-- So we add constraints to "a" by saying "Num a", this means whatever "a" is, it
 
-- must be in the Num type class.
 
   
instance Num a => Num [a] where
+
(f:fs) + (g:gs) = f+g : fs+gs -- (2)
-- Next, we have to implement all the operations that instances of Num support.
+
fs + [] = fs -- (3a)
-- A minimal set of operations is +, *, negate, abs, signum and fromInteger.
+
[] + gs = gs -- (3b)
xs + ys = zipWith' (+) xs ys
+
where
+
(f:fs) * (g:gs) = f*g : [f]*gs + fs*(g:gs) -- (4)
zipWith' f [] ys = ys
+
_ * _ = [] -- (5)
zipWith' f xs [] = xs
+
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys
+
abs = undefined -- I can't think of a sensible definition
-- We define a new version of zipWith that returns a list as long as the longest
+
signum = map signum
-- of the two lists it is given. If we did not do this then when we add polynomials
+
fromInteger n = [fromInteger n]
-- the result would be truncated to the length of the shorter polynomial.
+
negate = map (\x -> -x)
xs * ys = foldl1 (+) (padZeros partialProducts)
+
where
+
====Explanation====
partialProducts = map (\x -> [x*y | y <- ys]) xs
+
(1) puts lists into type class Num, the class to which operators + and * belong, provided the list elements are in class Num.
padZeros = map (\(z,zs) -> replicate z 0 ++ zs) . (zip [0..])
+
-- This function is sort of hard to explain.... basically [1,2,3] should correspond
+
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:
-- to the polynomial 1 + 2x + 3x^2. partialProducts does the steps of the multiplication
+
-- just like you would by hand when multiplying polynomials.
+
(f+x*fs) + (g+x*gs) = f+g + x*(fs+gs)
-- padZeros takes a list of polynomials and creates tuples of the form
+
(f+x*fs) * (g+x*gs) = f*g + x*(f*gs + fs*(g+x*gs))
-- (offset, poly). If you notice when you add the partial products by hand
+
-- that you have to shift the partial products to the left on each new line.
+
(3) and (5) handle list ends.
-- we accomplish this by padding by zeros at the beginning of the partial product.
+
-- Finally we use foldl1 to sum the partial products. Since they are polynomials
+
The bracketed <tt>[f]</tt> in (4) avoids mixed arithmetic, which Haskell doesn't support.
-- They are added by the definition of plus we already gave.
+
negate xs = map negate xs
+
====Comments====
abs xs = map abs xs -- is this reasonable?
+
signum xs = fromIntegral ((length xs)-1)
+
The methods are qualitatively different from ordinary array-based methods; there is no vestige of subscripting or counting of terms.
-- signum isn't really defined for polynomials, but polynomials do have a concept
+
-- of degree. We might as well reuse signum as the degree of the
+
The methods are suitable for on-line computation. Only
-- the polynomial. Notice that constants have degree zero.
+
<i>n</i> terms of each input must be seen before the <i>n</i>-th term
fromInteger x = [fromInteger x]
+
of output is produced.
-- This definition of fromInteger seems cyclical, it is left
+
-- as an exercise to the reader to figure out why it is correct :)
+
Thus the methods work on infinite series as well as polynomials.
</haskell>
+
The reader is encouraged to write a simple pretty printer that takes into account the many special cases of displaying a polynomial. For example, [1,3,-2, 0, 1,-1,0] should display as: <tt>-x^5 + x^4 - 2x^2 + 3x + 1</tt>
+
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,
   
Other execrises for the reader include writing <haskell>polyApply :: (Num a) => [a] -> a -> a </haskell> which evaluates the polynomial at a specific value or writing a differentiation function.
+
take 5 pascal -- [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]
   
 
See also
 
See also
 
* [[Pointfree]]
 
* [[Pointfree]]
* [http://darcs.haskell.org/numericprelude/src/MathObj/Polynomial.lhs NumericPrelude: Polynomials]
+
* [http://darcs.haskell.org/numericprelude/src/MathObj/Polynomial.hs NumericPrelude: Polynomials]
* [[Add Polynomials]]
+
* [[Add polynomials]]
 
* Solve differential equations in terms of [http://www.haskell.org/pipermail/haskell-cafe/2004-May/006192.html power series].
 
* Solve differential equations in terms of [http://www.haskell.org/pipermail/haskell-cafe/2004-May/006192.html power series].
   

Latest revision as of 13:42, 28 October 2013

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 him 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

[edit] 1 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)
  -- "1234567" -> ("1357", "246")
  -- the lazy match with ~ is necessary for efficiency, especially enabling 
  -- processing of infinite lists
  foldr (\a ~(x,y) -> (a:y,x)) ([],[])
 
  (map snd *** map snd) . partition (even . fst) . zip [0..]
 
  transpose . unfoldr (\a -> toMaybe (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
 
  -- 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.

[edit] 2 Mathematical sequences, etc

  -- factorial
  -- 6 -> 720
  product [1..6]
 
  foldl1 (*) [1..6]   -- this won't work for 0; use "foldl (*) 1 [1..n]" instead
 
  (!!6) $ scanl (*) 1 [1..]
 
  fix (\f n -> if n <= 0 then 1 else n * f (n-1))
 
 
  -- powers of two sequence
  iterate (*2) 1
 
  unfoldr (\z -> Just (z,2*z)) 1
 
 
  -- fibonacci sequence
  unfoldr (\(f1,f2) -> Just (f1,(f2,f1+f2))) (0,1)
 
  fibs = 0:1:zipWith (+) fibs (tail fibs)
 
  fib = 0:scanl (+) 1 fib -- also seen as: fibs = fix ((0:) . scanl (+) 1)
 
 
  -- pascal triangle
  pascal = iterate (\row -> zipWith (+) ([0] ++ row) (row ++ [0])) [1]
 
 
  -- prime numbers
  -- example of a memoising caf (??)
  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 = esieve [2..] where
            esieve (p:xs) = p : esieve (diff xs [p, p+p..])
 
  -- or if you want your n primes in less than n^1.5 time instead of n^2.2+
  peprimes = 2 : pesieve [3..] peprimes 4 where
                 pesieve xs (p:ps) q | (h,t) <- span (<q) xs 
                          = h ++ pesieve (diff t [q, q+p..]) ps (head ps^2)
 
  -- enumerating the rationals (see [1])
  rats :: [Rational]
  rats = iterate next 1 where
       next x = recip (fromInteger n+1-y) where (n,y) = properFraction x
 
  -- another way
  rats2 = fix ((1:) . (>>= \x -> [1+x, 1/(1+x)])) :: [Rational]

[1] Gibbons, Lest, Bird - Enumerating the Rationals

[edit] 3 Monad magic

The list monad can be used for some amazing Prolog-ish 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" >>= \a -> "45" >>= \b -> return [a,b]
 
  -- 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"
 
  fix ((1:) . (>>= \x -> [x+1, 1/(x+1)])) :: [Rational]
  [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 (.)) [(+1),(*2)] 500
 
 
  -- perform functions in/on a monad, lifting
  fmap (+2) (Just 2)
 
  liftM2 (+) (Just 4) (Just 2)
 
 
  -- [still to categorize]
  (id >>= (+) >>= (+) >>= (+)) 3        -- 3+3+3+3 = 12
                                        -- Note: 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 (+)
 
  (join . liftM2) (*) (+3) 5            -- (5+3)*(5+3) = 64
                                        -- Note: 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 }

[edit] 4 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
  -- requires 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 If-then-else.

[edit] 4.1 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)

[edit] 4.1.1 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.

[edit] 4.1.2 Comments

The methods are qualitatively different from ordinary array-based methods; there is no vestige of subscripting or counting of terms.

The methods are suitable for on-line computation. Only n terms of each input must be seen before the n-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