2

I thought -XStrict was supposed turn GHC into a Strict Haskell, so I tried the infinite Fibonacci sequence test

my_zipWith f  x [] = []
my_zipWith f []  y = []
my_zipWith f (x:xt) (y:yt) = f x y : my_zipWith f xt yt

test_fibs n = 
    let fibs = 0 : 1 : my_zipWith (+) fibs (tail fibs) in
    take n fibs

main = do
        putStr $ show $ test_fibs 15

to see if it would blow up in memory, but it doesn't:

$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 8.0.2

$ ghc -XStrict fibs.hs && ./fibs 
[1 of 1] Compiling Main             ( fibs.hs, fibs.o )
Linking fibs ...
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]

What am I doing wrong?

MWB
  • 11,740
  • 6
  • 46
  • 91
  • `Strict` roughly adds a strictness annotation `!` everywhere it can be added to _in your file_. Libraries compiled without that flag are unaffected. Here you use the standard list type `[a]` which remains non-strict. If you defined your own list type (and associated `zipWith`, `tail`, etc.) I guess you will obtain the behavior you expect (?). – chi Dec 24 '20 at 10:00
  • @chi I understood that from the answer. I'm just curious if it's possible to make `:`, `++`, `zipWith` and other List functions strict. – MWB Dec 25 '20 at 03:12
  • @MaxB: No, `[]` is defined as lazy. If you want strict versions of base types, there’s [`Data.Strict.List.List`](https://hackage.haskell.org/package/strict-base-0.4.0.0/docs/Data-Strict-List.html) from `strict-base` (although `vector` is preferable) and the [`strict`](https://hackage.haskell.org/package/strict) package for some others. These have instances of standard classes like `Foldable`. `zipWith` isn’t overloaded in `base` but there’s [`Zip`](https://hackage.haskell.org/package/keys-3.12.3/docs/Data-Key.html#t:Zip) in `keys` (split out from the older `category-extras`). – Jon Purdy Dec 28 '20 at 21:53

1 Answers1

4

Strict pragma certainly let GHC evaluate everything strictly, but into only Weak Head Normal Form. For example:

(a, b) = (error "a", error "b")

If above code exists under Strict pragma, any error arises. Let's see your code:

test_fibs n = 
    let fibs = 0 : 1 : my_zipWith (+) fibs (tail fibs) in
    take n fibs

fibs called recursively but in list cons, so now whole list is WHNF. That is reason why your code didn't stack.

This post will help you also. Enjoy recursion and laziness!

Add:

An easy way, to use deepseq:

{-# LANGUAGE Strict #-}
import Control.DeepSeq

my_zipWith f  x [] = []
my_zipWith f []  y = []
my_zipWith f (x:xt) (y:yt) = force $ f x y : my_zipWith f xt yt

test_fibs :: Int -> [Int]
test_fibs n = 
    let fibs = 0 : 1 : my_zipWith (+) fibs (tail fibs) in
    force $ take n fibs

main = do
        putStr $ show $ test_fibs 15

force defined as force x = x `deepSeq` x, deepSeq evaluate an expression deeply literally to NF (Normal Form). This conversion is achieved with GHC.Generics. If convert manually, just have to evaluate inside of data, so can rewrite following:

{-# LANGUAGE Strict #-}

my_zipWith f  x [] = []
my_zipWith f []  y = []
my_zipWith f (x:xt) (y:yt) = f x y : go
    where
        go = my_zipWith f xt yt

test_fibs n = 
    let
        fib2 = my_zipWith (+) fibs (tail fibs)
        fibs = 0 : 1 : fib2
    in
        take n fibs

main = do
        putStr $ show $ test_fibs 15

But they can't stack actually. Because GHC can detect infinite loop, but it's another story.

Akihito KIRISAKI
  • 1,243
  • 6
  • 12