(Coding) Pearls

Programming, Algorithms, Math.

Bird's book

"Pearls of Functional Algorithm Design", by Richard Bird. Cambridge University Press. 2010.
Great book!
Inspirational in it's succinct and clear way of presenting the material.
No wonder: It is a collection of some of the pearls published in the 20-years period (1990-2010) in the Journal of Functional Programming.

Coding Pearls in Haskell

  1. Dijkstra -- Shortest path in a graph (no heuristics).
  2. Needleman-Wunsch -- Global sequences alignment.
  3. Smith-Waterman -- Local sequences alignment.

  4. Clock -- Measuring execution time -- Easy. The goal is to time a ceratin function or program. Of course, there's difference between "wall-time" and "CPU time", and whether you want to count IO-Time as well (waiting for File I/O), multi-threads, and so on.
    1. System.CPUTime- Simplest. Coems with Base. clock1.hs
    2. Clock package - Various options for 'Time' definition. Also using the Formatting package for nicer output. clock2.hs
    3. Other possible packages : Timeit package, Criterion package.
    [0] http://chrisdone.com/posts/measuring-duration-in-haskell
    [1] http://rosettacode.org/wiki/Time_a_function#Haskell
  5. Random number(s).
  6. Formatting: Using Text.Printf - part of Base -- Easy. printf.hs
    -- Others options are available: Formatting package (opens in new window)
  7. Rooms map -- Creating a room map for an adventure game -- Random, SVG -- Med. roomsSVG.hs.
    An example result opens in a new tab: roomsSVG_Output.JPG.
  8. foldr and fusion -- Simple example of fusing function on foldr -- Med.
    Source code example: fusion1.hs.
    Fusion is the idea of combining (or 'fusing') a few operations together in a manner that avoids intemediate data-structures or claculations. This is a very common practice in functional programming, where fusion can improve dramatically performance.
    Basic text-definition of fusion for foldr is: " f*foldr g a = foldr h b ", Provided f is strict, f a = b, and f (g x y) = h x (f y) for all x and y.
    The fusion condition on "f strict" can be relaxed if we just want to use " f (foldr g a xs) = foldr h b xs ", for all finite sets xs.
    A note about foldr: " foldr:: (a->b->b) -> b -> [a] -> b " : Takes the second argument, and the last item of the list, and applies the function. Then, takes the result and the pentumilate element of the list, and repeats.
    For a more elaborated example, see the Celebrity Clique pearl (P9) in Bird's book.
  9. Triangular numbers -- Fiding all triangular numbers. triWizard.hs.
  10. Purple America -- Coloring the US/counties map based on voting. Full credit for this problem goes to nifty.stanford.edu (see link below). Printed from there the problem and slides: assignment and slides. And here are the files you need to run it: purpleAmerica.hs, USA.txt, USA2012.txt, and the results: purpleUSA.jpg.
    The full description is available here: http://nifty.stanford.edu/2014/wayne-purple-america/s.
  11. Jumble solver -- Given sequence of letters, find if they constitute a word. Jumble.hs. Here is also a text file containing all legal words wordsEn.txt
  12. Input from user -- Can be done through command-line-arguments, external file, or simple keyboard.
    -- For command-line-arguments, and file-input, see Jumble.hs
    -- For keyboard, see userInput.hs
  13. Wolf-and-Sheep -- AI game. Pawns .vs. Queen on a chess board. Who has the forced win? (spoiler alert: White).

Coding Pearls in Matlab

  1. Fractal Image Coding -- Using IFS (Iterated Functions system) to encode and decode an image. ifs_encode.m and ifs_decode.m. Sample images to use: lena.png, barbara.png, baboon.png.

Coding Pearls in Python

  1. (see in projects some practical examples)

Project E-u-l-e-r

Want to make sure I am not a spoiler, so am not linking to the original page and details.
The idea in most is to use some Math to make the coding (and solution) much simpler.

Update: Since first put over here, I started solving these serially (planning to clean the table, if possible), so removed it alltogether. If you want to discuss these, please reach out to me directly.

Questions/Comments: Zachi at Baharav dot Org .