Blow your mind
From HaskellWiki
m (→Mathematical sequences, etc) 

(40 intermediate revisions by 22 users not shown) 
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 (n1))  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+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
[edit] 3 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" >>= \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`(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 (+) (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 Ifthenelse.
[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 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.