Correcting Towers of Hanoi Haskell Solution

I've been really having fun playing with Haskell. I found a solution via Wikipedia for the Towers of Hanoi. The solution is here http://www.kernelthread.com/projects/hanoi//html/hs.html.



This solution will not compile with ghci v6.12.1. This is the corrected solution I tested and confirmed works with ghci v6.12.1:



dohanoi :: (Num a) => a -> a -> a -> a -> [(a,a)]

dohanoi 0 _ _ _ = []

dohanoi n from to using = let m=n-1

in dohanoi m from using to ++ [(from,to)] ++ dohanoi m using to from



hanoi :: (Num a) => a -> [(a,a)]

hanoi n = dohanoi n 1 3 2

Parsing notes

Top-down vs. bottom-up

Top-down(e.g. ANTLR) is a left most derivation(LL)
Implemented as a recursive-descent algorithm
Finds next node in left sentential form where a non-terminal is replaced with its equivalent RHS.

Bottom-up(such as yacc or parsec) is a right most derivation(LR)
Find a non-terminal in right sentential form such that non-terminal can be replaced with its equivalent LHS.

Complexity of parsing algorithms ususally O(n^3)

LL parsers cannot handle left-recursion. e.g. A->A+B will never stop
left-recursion is a rule where the LHS rule name is also on the RHS.

Pairwsie disjoint test used to evaluate a grammar if it can be LL parsed.
If a rule passes the pairwise disjoint test, then this means no RHS of a rule has a common terminal token.

left factoring(grouping common terminal/non-terminals together toward the left side) can help wiht LL parsers but not in all cases.

LR usually implemented as shift reduce algorithms.
LR advantages:

1. Works for almost all grammars
2. Works on more grammars than most other bottom-up algorithms
3. Syntax errors detected early
4. LR grammars are a superset of the grammars parsable by LL grammars