On Monday, August 11, 2014 8:30:32 AM UTC+5:30, Steven D'Aprano wrote: > You did the same thing in your own course, the only difference being you > accepted a different set of primitive functions. But ultimately you have to > introduce *some* amount of concreteness, at some level, otherwise we're > just engaged in mental masturbation:
> Q: "Write a function to calculate the nth Catalan number." > A: "Assume that a function Catalan(n) exists and calculates the nth Catalan > number. Then the solution is Catalan." You're concocting your own definitions and critiquing/refuting them. Here is the Haskell definition [Ive modernized my '93 code]. It corresponds to the 4th interpretation from http://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics -- applications of a bin op to a 'full' binary tree All of 3 lines! data Tree a = I (Tree a) (Tree a) | L a deriving Show c [x]= [L x] c ls = [I x y | i<-[1..length ls -1], let (l,r) = splitAt i ls, x <- c l, y <- c r] Read 'L' as Leaf Node 'I' as Internal Node 'c' as the catalan enumerator splitAt splits a list at a position: *Main> splitAt 3 [3,4,5,6,7] ([3,4,5],[6,7]) And some example runs *Main> c [] [] *Main> c [1] [L 1] *Main> c [1,2] [I (L 1) (L 2)] *Main> c [1,2,3] [I (L 1) (I (L 2) (L 3)),I (I (L 1) (L 2)) (L 3)] *Main> c [1,2,3,4] [I (L 1) (I (L 2) (I (L 3) (L 4))),I (L 1) (I (I (L 2) (L 3)) (L 4)),I (I (L 1) (L 2)) (I (L 3) (L 4)),I (I (L 1) (I (L 2) (L 3))) (L 4),I (I (I (L 1) (L 2)) (L 3)) (L 4)] *Main> Opening up the last eg into separate lines: [I (L 1) (I (L 2) (I (L 3) (L 4))), I (L 1) (I (I (L 2) (L 3)) (L 4)), I (I (L 1) (L 2)) (I (L 3) (L 4)), I (I (L 1) (I (L 2) (L 3))) (L 4), I (I (I (L 1) (L 2)) (L 3)) (L 4)] -- https://mail.python.org/mailman/listinfo/python-list
