When I compile the following program with -O -prof using ghc-2.05 on
a 686 linux box :
module Main ( main ) where
f :: Int
f = length [1..1000000]
main = print (f + f + f + f)
I get :
Main.o(.text+0x9c): undefined reference to `PrelBase_Z36g3J_fast3'
I am trying to determine to what extent ghc approximates full laziness
- if I profile without optimisation that is not an accurate
indication. I don't think any higher-order language can be fully
lazy, since sometimes evaluation of higher-order functions would lead
to a sub-expression identical to one that had already been evaluated
and the system would have no way to know this (trying to detect it
would seem akin to higher-order unification). I hope that, apart from
this caveat, ghc is fully lazy, but hope is not a sufficient basis for
writing programs. The presence or absence of laziness could alter
the order of an algorithm.
The program below compiles and links with -O -prof, but seg-faults
during execution (it is fine with just -prof) :
module Main ( main ) where
ls :: Int -> [[Int]]
ls n = map (\n -> [n..(100000 + n - 1)]) [1..n]
plusOnes :: [Int] -> [Int]
plusOnes = map (+1)
-- applies plusOnes to the n+1th element of the list
-- most of list is unchanged
foo :: Int -> [[Int]] -> [[Int]]
foo n xs = take n xs ++ (plusOnes (head (drop n xs)) : tail (drop n xs))
-- generates a list of applications of foo to input, for each value of n
-- each element of the output is identical to the other elements in all but one of its
sub-lists
bar :: [[Int]] -> [[[Int]]]
bar xs = map (flip foo xs) [0 .. length xs - 1]
-- for each sub-list, computes the sum of the lengths of its sub-lists
-- running time should be O(n) for a lazy machine, O(n**2) for an eager one
-- seems to actually run in O(n * log n): 0.16s for 1 sub-list, 0.42s for 2, 1.32 for 4
baz :: [[[Int]]] -> [Int]
baz = map (sum . map length)
main = do putStr "how many sublists ? "
r <- getLine
let n = read r
print ((baz . bar) (ls n))
Tim
--
----------------------------------------------------------------------
T.R.BARBOUR Email : [EMAIL PROTECTED]
----------------------------------------------------------------------
Department of Computer Science
The University of Melbourne
Parkville, Victoria 3052
Australia
----------------------------------------------------------------------
