gistfile1.hs

{-
problem: generate infinite list of triples by height, i.e.:

[(1,1,1), (1,1,2), (1,2,1), (2,1,1), (1,1,3), ... ]
-}

import Data.List (nub, inits)

-- inefficient (exponential):
triples :: Int -> [(Int, Int, Int)]
triples n = [(a, b, c) | a <- [1..n-1], b <- [1..n-a], c <- [1..n-a-b], a+b+c == n]

-- also inefficient (exponential):
triples' 3 = [(1, 1, 1)]
triples' n = (nub . concat) [[(a, b, c+1), (a, b+1, c), (a+1, b, c)] | (a, b, c) <- triples' (n - 1)]

-- cool trick:
prod2' l1 l2 = [(a, b) | (as, bs) <- zip (inits l1) (inits l2), (a, b) <- zip as (reverse bs)]

-- but, it doesn't quite generalise to triples:
prod2 l1 l2 = [a:b | (as, bs) <- zip (inits l1) (inits l2), (a, b) <- zip as (reverse bs)]

prodN [] = []
prodN [x] = map (:[]) x
prodN (x:xs) = prod2 x (prodN xs)