Anonymous user
Catalan numbers/Pascal's triangle: Difference between revisions
Haskell version.
(→{{header|Ruby}}: Rubyfy and simplify) |
(Haskell version.) |
||
Line 315:
14 2674440
15 9694845
</pre>
=={{header|Haskell}}==
As required by the task this implementation extracts the Catalan numbers from Pascal's triangle, rather
than calculating them directly. Also, note that it (correctly) produces [1, 1] as the first two numbers.
<lang haskell>import System.Environment (getArgs)
-- Pascal's triangle.
pascal :: [[Integer]]
pascal = [1] : map (\row -> 1 : zipWith (+) row (tail row) ++ [1]) pascal
-- The Catalan numbers from Pascal's triangle. This uses a method from
-- http://www.cut-the-knot.org/arithmetic/algebra/CatalanInPascal.shtml
-- (see "Grimaldi").
catalan :: [Integer]
catalan = map (diff . uncurry drop) $ zip [0..] (alt pascal)
where alt (x:_:zs) = x : alt zs -- every other element of an infinite list
diff (x:y:_) = x - y
diff (x:_) = x
main :: IO ()
main = do
ns <- fmap (map read) getArgs :: IO [Int]
mapM_ (print . flip take catalan) ns</lang>
{{out}}
<pre>
./catalan 15
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
</pre>
| |||