标签: weak-head-normal-form

什么是弱头范式(WHNF)是什么意思？什么是头标准型(HNF)和范式(NF)是什么意思？

真实世界Haskell说:

熟悉的seq函数将表达式计算为我们称之为head normal form(缩写为HNF)的表达式.它一旦到达最外面的构造函数("头部")就会停止.这与正常形式(NF)不同,其中表达式被完全评估.

您还将听到Haskell程序员引用弱头正常形式(WHNF).对于正常数据,弱头正常形式与头部正常形式相同.差异只出现在功能上,而且我们在这里无关紧要.

我已经阅读了一些资源和定义(Haskell Wiki和Haskell邮件列表和自由词典),但我没有得到它.有人可能举一个例子或提供外行定义吗？

我猜它会类似于:

WHNF = thunk : thunk

HNF = 0 : thunk 

NF = 0 : 1 : 2 : 3 : []

如何做seq和($!)与WHNF和HNF有关？

更新

我还是很困惑.我知道有些答案会忽略HNF.通过阅读各种定义,似乎WHNF和HNF中的常规数据之间没有区别.但是,它似乎与功能有所区别.如果没有差异,为什么还seq需要foldl'？

另一个混淆点来自Haskell Wiki,它指出seq减少到WHNF,并且对以下示例不做任何处理.然后他们说他们必须seq用来强迫评估.那不是强迫它到HNF吗？

常见的新手堆栈溢出代码:

myAverage = uncurry (/) . foldl' (\(acc, len) x -> (acc+x, len+1)) (0,0)

Run Code Online (Sandbox Code Playgroud)

了解seq和弱头正常形式(whnf)的人可以立即明白这里出了什么问题.(acc + x,len + 1)已经在whnf中,所以seq将值减少到whnf,对此无效.这段代码将像原始的foldl示例一样构建thunks,它们只是在元组内部.解决方案只是强制元组的组件,例如

myAverage …

Run Code Online (Sandbox Code Playgroud)

我一直在玩Simon Marlow关于Haskell中的并行和并发编程的书中的一些例子,偶然发现了一个我不太了解的有趣行为.这真的是我试图了解GHC的一些内部运作方式.

假设我在REPL中执行以下操作:

?» let x = 1 + 2 :: Int
?» let z = (x,x)
?» :sprint x
x = _
?» :sprint z
z = (_,_)
?» seq x ()
()
?» :sprint z
z = (3,3)

好吧,这几乎是我的预期,除了z已经被评估为WHNF.让我们编写一个类似的程序并将其放在一个文件中:

module Thunk where

import Debug.Trace

x :: Int
x = trace "add" $ 1 + 2

z :: (Int,Int)
z = (x,x)

在GHCi中摆弄它:

?» :sprint x
x = _
?» :sprint z
z = _
?» seq x () …

我从真实世界的 Haskell 中读到

它的操作如下：当一个seq表达式被求值时，它会强制求值它的第一个参数，然后返回它的第二个参数。它实际上对第一个参数没有任何作用：seq仅作为强制评估该值的一种方式存在。

我在那里强调了then因为对我来说它意味着两件事发生的顺序。

从Hackage我读到

seq a b如果a是底部，则的值是底部，否则等于b。换句话说，它将第一个参数评估a为弱头部范式（WHNF）。seq 通常用于通过避免不必要的懒惰来提高性能。

关于求值顺序的注意事项：表达式seq a b不保证a会在 之前求值b。by 给出的唯一保证seq是两者a和b将在seq返回值之前进行评估。特别是，这意味着b可以在 之前进行评估a。[…]

此外，如果我# Source从那里点击链接，页面不存在，所以我看不到seq.

这似乎与此答案下的评论一致：

[…]seq不能在普通的 Haskell 中定义

另一方面（或在同一方面，真的），另一条评论写道：

“真实”seq在 GHC.Prim 中定义为seq :: a -> b -> b; …

在Haskell中,是否可以测试一个值是否已被评估为弱头正常形式？如果一个函数已经存在,我希望它有一个像这样的签名

evaluated :: a -> IO Bool

有一些类似功能的地方.

一个以前的答案给我介绍:sprintghci的命令,该命令将打印已经被迫弱头部正常形态的值只有部分.:sprint可以观察是否已评估某个值:

> let l = ['a'..]
> :sprint l
l = _
> head l
'a'
> :sprint l
l = 'a' : _

有可能IO检查本来是禁止的属性.例如,可以比较IO以查看两个值是否来自同一声明.这是由StableNames in提供System.Mem.StableName并用于解决数据统一中的可观察共享问题.相关内容StablePtr未提供检查引用值是否为弱头正常形式的机制.

Haskell 定义说:

表达式是弱头正常形式(WHNF),如果它是:

• 一个构造函数(最终应用于参数),如True,Just(square 42)或(:) 1
• 一个内置函数应用于太少的参数(可能没有),如(+)2或sqrt.
• 或lambda抽象\ x - >表达式.

为什么内置功能会得到特殊处理？根据lambda演算,部分应用函数和任何其他函数之间没有区别,因为最后我们只有一个参数函数.

我被一些烦人的事情绊倒了。我知道 haskell 与弱头部范式 (WHNF) 一起工作，我知道这是什么。将以下代码输入 ghci（我正在使用命令 :sprint 将表达式简化为 WHNF，据我所知。）：

let intlist = [[1,2],[2,3]]
:sprint intlist

给intlist = _这使得完全意义的我。

let stringlist = ["hi","there"]
:sprint stringlist 

给stringlist = [_,_] 这个已经让我困惑。但是之后：

let charlist = [['h','i'], ['t','h','e','r','e']]
:sprint charlist

出人意料地给出 charlist = ["hi","there"]

据我了解 Haskell，字符串只不过是字符列表，这似乎是通过检查类型"hi" :: [Char]和['h','i'] :: [Char].

我很困惑，因为根据我的理解，上面的所有三个示例或多或少都相同（列表列表），因此应该减少到相同的 WHNF，即 _。我错过了什么？

谢谢

我无法解释以下行为:

Prelude> let x = 1 + 2
Prelude> let y = (x,x)
Prelude> :sprint y
Prelude> y = _

现在,当我为x指定一个类型时:

Prelude> let x = 1 + 2 ::Int
Prelude> let y = (x,x)
Prelude> :sprint y
Prelude> y = (_,_)

为什么x的类型规范强制y为其弱头正规形式(WHNF)？

我在阅读Simon Marlow在Haskell中的并行和并发编程时偶然发现了这种行为.

在一个简单的例子中,通过打印将WHNF转换为NF可以正常工作

Prelude> let x = 1 + 2 :: Int
Prelude> :sprint x
x = _
Prelude> x
3
Prelude> :sprint x
x = 3

但在某种情况下,类型未声明它不起作用.

Prelude> let x = 1 + 2
Prelude> :sprint x
x = _
Prelude> x
3
Prelude> :sprint x
x = _

你能解释为什么转换在最后一种情况下不起作用吗？

在Haskell中,lambdas被认为是在WHNF中,而未应用的用户定义函数则不是.这种区别背后的动机是什么？

我读过很多关于弱头正常形式和seq的书.但是我仍然无法想象Haskell评估顺序背后的逻辑

一个常见的例子说明何时以及如何使用,但我仍然不明白常见的例子

foldl (+) 0 [1..5000000]

可能导致堆栈溢出.而使用另一种折叠定义seq则没有

foldl' _ a [] = a
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
foldl' (+) 0 [0..5000000]

从我读过的seq的解释,作者非常谨慎地做出如下清楚:

• 第一个参数seq不能保证在第二个参数之前进行求值
• 第一个参数seq只会被评估为弱头正常形式
• seq只有当第二个参数被评估为WHNF时才会对第一个参数进行评估

那么,如果以上是正确的(是吗？)那么为什么不foldl'溢出foldl呢？

当我们减少一步时,不应该看起来像这样,对吧？

foldl' (+) 0 (1:xs) = let a' = (+) 0 1 in a' `seq` foldl' (+) a' xs

在上面,seq由于存在需要完成的功能应用,因此第二个参数不在WHNF中.seq在我们达到第二个参数的WHNF之前,我们是否可以保证评估此处的第一个参数？

我有这个代码:

import Data.List

newList_bad  lst = foldl' (\acc x -> acc ++ [x*2]) [] lst
newList_good lst = foldl' (\acc x -> x*2 : acc) [] lst

这些函数返回列表,每个元素乘以2:

*Main> newList_bad [1..10]
[2,4,6,8,10,12,14,16,18,20]
*Main> newList_good [1..10]
[20,18,16,14,12,10,8,6,4,2]

在ghci:

*Main> sum $ newList_bad [1..15000]
225015000
(5.24 secs, 4767099960 bytes)
*Main> sum $ newList_good [1..15000]
225015000
(0.03 secs, 3190716 bytes)

为什么newList_bad功能比它慢200倍newList_good？我知道这不是一个很好的解决方案.但为什么这个无辜的代码工作得如此之慢？

这是什么"4767099960字节"?? 对于那个简单的操作,Haskell使用4 GiB ??

编译后:

C:\1>ghc -O --make test.hs
C:\1>test.exe
225015000
Time for sum (newList_bad [1..15000]) is 4.445889s …

我必须将以下lambda表达式减少为WHNF,但我不太清楚如何做到这一点:

(?x y. x 3) (+ 4) (+ 6 7)

那么,我该怎么做？呼叫减少名称？

这个表达式(其他例子)(?z x. (?x. x) z) x在WHNF中了吗？

我发现很难理解Haskell如何评估这个primes函数.是的primes功能得到评估一遍又一遍,或primes在primeFactors功能将指向回到第一primes？

primes = 2 : filter ((==1) . length . primeFactors) [3,5..]

primeFactors n = factor n primes
  where
    factor n (p:ps)
        | p * p > n        = [n]
        | n `mod` p == 0   = p : factor (n `div` p) (p:ps)
        | otherwise        = factor n ps

main :: IO ()
main = print $ length . take 100000 $ primes