Created
November 15, 2012 19:53
-
-
Save mmakowski/4080823 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{- | |
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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment