data T = N T T | L deriving Show
⠀
ts :: Int -> [T]
ts 1 = [L]
ts k | (n, 1) <- divMod k 2 = [N x y | i <- [1..n ], x <- ts i, y <- ts (k-i)]
ts k | (n, 0) <- divMod k 2 = [N x y | i <- [1..n-1], x <- ts i, y <- ts (k-i)]
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀++ [N x y | ys@(x:_) <- tails (ts n), y <- ys]
⠀
⠀
<Gurkenglas> > ts 4
<lambdabot> [N L (N L (N L L)),N (N L L) (N L L)]
(Beware, I had to use U+2800 to almost align the code block in spite of LW’s software eating whitespace. Source here)
Not really, the sequence grows quickly enough to outstrip the recursive overhead. To calculate the overhead, replace the * in f(i)*f(2n+1-i) with a +. Memoizing is of course trivial anyway, using memoFix.
The same control flow generates them. In Haskell:
(Beware, I had to use U+2800 to almost align the code block in spite of LW’s software eating whitespace. Source here)
Edit: See also: oeis, where you enter an integer sequence and it tells you where people have seen it.
Very well, congratulations again!
Perhaps a nonrecursive function would be faster.
Not really, the sequence grows quickly enough to outstrip the recursive overhead. To calculate the overhead, replace the
*inf(i)*f(2n+1-i)with a+. Memoizing is of course trivial anyway, using memoFix.