how to get the ordinal number in list

[Rustom Mody]

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)]