6

在 Haskell 中，以下代码打印“[1,2,3,4,5”：

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

但是在 Frege 中，它会抛出OutOfMemoryError以下代码：

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

这里唯一的区别是unpacked转换 fromString和[Char]FWIW 所需的函数，该unpacked函数是急切的。为什么整个表达式不能像 Haskell 中那样懒惰？是否有可能在 Frege 中实现类似于 Haskell 的东西？

4

5 回答 5

7

我不知道弗雷格，但根据语言定义String，你不能构建无限长的字符串（内存不足问题可能与渴望java.lang.String无关）。unpack

因为您知道 的每个元素numbersFrom 1将显示为至少 1 个字符，所以您可以过度估计列表的大小以显示然后解包，然后获取所需字符的数量：

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

或更一般地说：

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

如果您的枚举很昂贵，那么您可以开始考虑逗号、空格等的数量，并将参数减少到 second take，但您明白了。

于 2012-08-15T01:49:36.700 回答
6

我没有使用过弗雷格，但在我看来，如果unpacked是严格的，那么它的参数不应该是一个无限列表。尝试unpacked $ take 10代替take 10 $ unpacked.

于 2012-08-15T01:23:32.090 回答
4

这将不起作用，因为（不是）由 . 生成的无限字符串show。您需要一些帮助函数将列表转换为Char.

对此有一个标准功能可能会很好。

编辑 2013 年 2 月 22 日

类Show现在有一个新方法：

{--
    '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

导致的 Haskell 代码OutOfMemoryError现在可以写成：

(println . packed . take 10 . showChars ) [1..]
于 2012-08-15T08:16:46.637 回答
4

添加到其他答案，

由于show返回 a java.lang.String，因此无法显示无限列表。所以我想我可以写一个不同版本的 show 来返回 a [Char]。这就是我想出的，它正在发挥作用。

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

现在问题中的代码变得类似于 Haskell，并且不会因 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
于 2012-08-16T00:11:16.973 回答
2

简短的回答：字符串在 Frege 中是严格的，但在 Haskell 中是惰性的。

列表在两种语言中都是惰性的。但是在弗雷格中，字符串不是列表。

于 2012-08-17T09:33:09.577 回答