Expression eager in Frege but lazy in Haskell?

Question

In Haskell, the following code prints "[1,2,3,4,5":

foo = take 10 $ show $ numbersFrom 1 where 
  numbersFrom start = start : numbersFrom (start + 1) -- could use [1..]

But in Frege, It throws OutOfMemoryError with the following code:

foo = take 10 $ unpacked $ show $ numbersFrom 1 where
  numbersFrom start = start : numbersFrom (start + 1)

Here the only difference is the unpacked function which is necessary to convert from String to [Char] and FWIW, the unpacked function is eager. Why can't the whole expression be lazy as in Haskell? Is it possible to achieve something similar to Haskell in Frege here?

Answer 1

I haven’t used Frege, but it seems to me that if unpacked is strict, then its argument ought not be an infinite list. Try unpacked $ take 10 instead of take 10 $ unpacked.

Answer 2

I don't know Frege, but according to the language definition String is java.lang.String so you can't build infinitely long strings (the out of memory issue probably has nothing to do with unpack being eager).

Because you know each element of numbersFrom 1 will be shown as at least 1 character then you can over-approximate the size of the list to show then unpack, then take the number of desired characters:

foo = take 10 $ unpacked $ show $ take 10 $ numbersFrom 1 where
  numbersFrom start = start : numbersFrom (start + 1)

Or more generally:

n = 10 -- number of characters to show
m = 1  -- minimum (map (length . show) xs) for some type of xs
foo :: a -> [Char]
foo = take n . unpack . show . take ((n+m-1) `div` m) . someEnumeration
  where
  someEnumeration :: a -> [a]
  someEnumeration = undefined

If your enumeration is expensive then you can start taking into account the number of commas, whitespace, etc and reduce the argument to the second take, but you get the idea.

Answer 3

Adding to other answers,

Since show returns a java.lang.String, it is not possible to show infinite lists. So I thought I could write a different version of show to return a [Char] instead. This is what I have come up with and it is working.

frege> :paste
class AltShow a where
  altshow :: a -> [Char]

instance AltShow AltShow a => [a] where
  altshow [] = []
  altshow xs = concat $ (['['] : intersperse [','] ys) ++ [[']']] where
    ys = map altshow xs

instance AltShow Int where
  altshow = unpacked <~ show

intersperse :: a -> [a] -> [a]
intersperse _ [] = []
intersperse _ (x:[]) = [x]
intersperse sep (x : y : []) = 
  x : sep : y : []
intersperse sep (x : y : rest) = 
  x : sep : y : sep : intersperse sep rest
:q
Interpreting...

frege> altshow [1, 10, 2, 234]
res3 = ['[', '1', ',', '1', '0', ',', '2', ',', '2', '3', '4', ']']
frege> :t res3
res5 :: [Char]
frege> packed res3
res6 = [1,10,2,234]
frege> :t res6
res7 :: String

Now the code in the question becomes similar to Haskell and it is not exploding with OutOfMemoryError:

frege> :paste
foo = take 10 $ altshow $ numbersFrom 1 where
  numbersFrom start = start : numbersFrom (start + 1)
:q
Interpreting...

frege> foo
res9 = ['[', '1', ',', '2', ',', '3', ',', '4', ',', '5']
frege> packed foo
res11 = [1,2,3,4,5

Answer 4

This will not work because of the infinite string that is (not) being produced by show. You would need some helper function that converts a list to a list of Char.

It would probably be good to have a standard function for this.

---

Edit Feb 22th 2013

Class Show has now a new method:

{--
    'showChars' addresses the problem of 'show'ing infinite values.
    Because 'show' has type 'String' and 'String' is atomic, this would
    try to create a string with infinite length, and hence is doomed to fail.

    The default definition is

    > showChars = String.toList . show

    This is ok for all finite values. But instances for recursive types
    should implement it in a way that produces a lazy list of characters.

    Here is an example for the list instance:

    > showChars [] = ['[', ']']
    > showChars xs = '[' : ( tail [ c | x <- xs, c <- ',' : showChars x ] ++ [']'] )

-}
showChars :: show -> [Char]
showChars = String.toList . show

The Haskell code that led to the OutOfMemoryError can now be written as:

(println . packed . take 10 . showChars ) [1..]

Answer 5

Short answer: Strings are strict in Frege, but lazy in Haskell.

Lists are lazy in both languages. But in Frege, Strings are not lists.