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?

Recha

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.

Affiance

Strings in Frege are not lists. So take 10 cannot be applied to the result of show. Hence unpacked is used to first convert from String to [Char] and then take 10 is applied on the list. – Recha

So what are Strings in Frege? It appears they are java.lang.String (see the Frege Language definition). You will never get around to evaluating unpack as it will never be able to build the string! – Unhandy

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.

Unhandy

Answer 3

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..]

Thruway

Answer 4

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

Recha

I think we could add a class operation to Show that does it this way and whose default implementation is toList <~ show – Thruway

Yes, that is a better way. Thanks. – Recha

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.

Opportuna