gpt4 book ai didi

haskell - 为什么 `data` 会导致无限循环,而 `newtype` 不会

转载 作者:行者123 更新时间:2023-12-04 03:35:41 25 4
gpt4 key购买 nike

我在学习Arrow按照教程 programming with arrows .我根据论文输入了以下代码,除了 SFdata 定义,而不是 newtype和论文中一样(实际上,我做了这个更改是偶然的,因为我是从内存中输入代码的):

import Control.Category
import Control.Arrow
import Prelude hiding (id, (.))

data SF a b = SF { runSF :: [a] -> [b] } -- this is the change, using data instead of newtype as in the paper

-- The folowing code is the same as in the paper
instance Category SF where
id = SF $ \x -> x
(SF f) . (SF g) = SF $ \x -> f (g x)

instance Arrow SF where
arr f = SF $ map f
first (SF f) = SF $ unzip >>> first f >>> uncurry zip

instance ArrowChoice SF where
left (SF f) = SF $ \xs -> combine xs (f [y | Left y <- xs])
where
combine (Left _ : ys) (z:zs) = Left z : combine ys zs
combine (Right y : ys) zs = Right y : combine ys zs
combine [] _ = []

delay :: a -> SF a a
delay x = SF $ init . (x:)

mapA :: ArrowChoice a => a b c -> a [b] [c]
mapA f = arr listcase >>>
arr (const []) ||| (f *** mapA f >>> arr (uncurry (:)))

listcase :: [a] -> Either () (a, [a])
listcase [] = Left ()
listcase (x:xs) = Right (x, xs)

当我在 ghci 中加载文件时并执行 runSF (mapA (delay 0)) [[1,2,3],[4,5,6]] ,它会触发一个无限循环并最终耗尽内存。如果我改变 data返回 newtype , 一切都好。同样的问题发生在 ghc 8.0.2、8.2.2 和 8.6.3 中。

即使我将代码编译成可执行文件,同样的问题也存在。

我想过 data之间的区别和 newtype ,当定义只有一个字段的数据结构时,是运行时成本。但这个问题似乎暗示了它们之间的更多差异。或者我可能没有注意到 Arrow 的某些内容。类型类。

任何人都可以有任何想法吗?非常感谢!

最佳答案

让我们看看这个例子。

data A = A [Int]
deriving (Show)

cons :: Int -> A -> A
cons x (A xs) = A (x:xs)

ones :: A
ones = cons 1 ones

我们预计 ones应该是 A [1,1,1,1...] , 因为我们所做的只是将列表包装在 data 中构造函数。但我们会错的。回想一下, data 的模式匹配是严格的。构造函数。也就是说, cons 1 undefined = undefined而不是 A (1 : undefined) .因此,当我们尝试评估 ones , cons模式匹配它的第二个参数,这导致我们评估 ones ... 我们出现了问题。
newtype不要这样做。在运行时 newtype构造函数是不可见的,所以就好像我们在普通列表上编写了等效程序
cons :: Int -> [Int] -> [Int]
cons x ys = x:ys

ones = cons 1 ones

这是非常有效的,因为当我们尝试评估 ones ,有一个 :我们与 ones 的下一个评估之间的构造函数.

你可以找回 newtype通过使您的数据构造函数模式匹配惰性来实现语义:
cons x ~(A xs) = A (x:xs)

这是您的代码的问题(我在做这件事时遇到了这个确切的问题)。有几个原因 data模式匹配默认是严格的;我看到的最引人注目的是,如果类型有多个构造函数,那么模式匹配将是不可能的。为了修复一些细微的 GC 泄漏,惰性模式匹配也有少量的运行时开销;评论中链接的详细信息。

关于haskell - 为什么 `data` 会导致无限循环,而 `newtype` 不会,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55448666/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com