binary-trees Haskell GHC #2 program
source code
--
-- The Computer Language Benchmarks Game
-- https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
--
-- Contributed by Daniel Smith
--
import Data.Foldable (for_)
import Data.Monoid ((<>))
import System.Environment (getArgs)
main :: IO ()
main = do
n <- read . head <$> getArgs
let stretchN = n + 1
stretchT = make stretchN
putStrLn . makeOutput "stretch tree" stretchN $ check stretchT
stretchT `seq` pure ()
let longT = make n
longC = check longT
longC `seq` pure ()
for_ [4, 6 .. n] $ \d -> do
let c = 16 * 2 ^ (n - d)
putStrLn . makeOutput (show c <> "\t trees") d $ sumT c d
longT `seq` pure ()
putStrLn $ makeOutput "long lived tree" n longC
makeOutput :: String -> Int -> Int -> String
makeOutput p n c = p <> " of depth " <> show n <> "\t check: " <> show c
data Tree = Nil | Node Tree Tree
sumT :: Int -> Int -> Int
sumT = go 0
where
go s 0 _ = s
go s c d = s' `seq` t `seq` go s' (c - 1) d
where
t = make d
s' = s + check t
check :: Tree -> Int
check Nil = 0
check (Node l r) = 1 + check l + check r
make :: Int -> Tree
make 0 = Node Nil Nil
make n = Node (make $ n - 1) (make $ n - 1)
notes, command-line, and program output
NOTES:
64-bit Ubuntu quad core
The Glorious Glasgow Haskell Compilation System,
version 8.8.1
Tue, 05 May 2020 21:29:15 GMT
MAKE:
mv binarytrees.ghc-2.ghc binarytrees.ghc-2.hs
/opt/src/ghc-8.8.1/bin/ghc --make -fllvm -O2 -XBangPatterns -threaded -rtsopts binarytrees.ghc-2.hs -o binarytrees.ghc-2.ghc_run
Loaded package environment from /home/dunham/.ghc/x86_64-linux-8.8.1/environments/default
[1 of 1] Compiling Main ( binarytrees.ghc-2.hs, binarytrees.ghc-2.o )
You are using an unsupported version of LLVM!
Currently only 7 is supported.
We will try though...
Linking binarytrees.ghc-2.ghc_run ...
rm binarytrees.ghc-2.hs
21.66s to complete and log all make actions
COMMAND LINE:
./binarytrees.ghc-2.ghc_run +RTS -N4 -K128M -H -RTS 21
PROGRAM OUTPUT:
stretch tree of depth 22 check: 8388607
2097152 trees of depth 4 check: 65011712
524288 trees of depth 6 check: 66584576
131072 trees of depth 8 check: 66977792
32768 trees of depth 10 check: 67076096
8192 trees of depth 12 check: 67100672
2048 trees of depth 14 check: 67106816
512 trees of depth 16 check: 67108352
128 trees of depth 18 check: 67108736
32 trees of depth 20 check: 67108832
long lived tree of depth 21 check: 4194303