Difference between revisions of "Blow your mind"
(Found a bug of sorts in one of these. Anyone care to fix it? Beyond me, I'm afraid so added a note.) 
m (fixed splitting into words using foldr) 

Line 14:  Line 14:  
words 
words 

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

−   there is a bug in this code in that two spaces in a row causes it to ignore the rest of the String 

−   "hello world" > ["hello"] 

−   sorry my Haskell isn't good enough to fix it! 

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)) 
Revision as of 04:28, 16 January 2007
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
List/String Operations
 split at whitespace
 "hello world" > ["hello","world"]
words
unfoldr (\b > fmap (const . (second $ drop 1) . break (==' ') $ b) . listToMaybe $ b)
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
 splitting into lists of length N
 "1234567" > ["12", "34", "56", "7"]
unfoldr (\a > toMaybe (null a) (splitAt 2 a))
takeWhile (not . null) . unfoldr (Just . splitAt 2)
 sorting by a custom function
 length > ["abc", "ab", "a"] > ["a", "ab", "abc"]
comparing f x y = compare (f x) (f y)
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
Mathematical Sequences, etc
 factorial
 6 > 720
product [1..6]
foldl1 (*) [1..6]
(!!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
 pascal triangle
pascal = iterate (\row > zipWith (+) ([0] ++ row) (row ++ [0])) [1]
 prime numbers
 example of a memoising caf (??)
primes = sieve [2..] where
sieve (p:x) = p : sieve [ n  n < x, n `mod` p > 0 ]
unfoldr sieve [2..] where
sieve (p:x) = Just(p, [ n  n < x, n `mod` p > 0 ])
 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
 x > y = diff xl ys
 otherwise = diff xs ys
esieve [] = []
esieve (p:ps) = p:esieve (diff ps (iterate (+p) p))
eprimes = esieve [2..]
 enumerating the rationals (see [1])
rats :: [Rational]
rats = iterate next 1 where
next x = recip (fromInteger n+1y) where (n,y) = properFraction x
[1] Gibbons, Lest, Bird  Enumerating the Rationals
Monad Magic
 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
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"
 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
(join . liftM2) (*) (+3) 5  64
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
 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
{
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, ...)
}
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)
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]
See also
 Pointfree
 NumericPrelude: Polynomials
 Add Polynomials
 Solve differential equations in terms of power series.