How does take 2 $ [1..] work in haskell?
We know that the $ operator binds the loosest, and also associates to the right, which means, [1..] should be evaluated first, and hence, shouldn't it run into an infinite loop? Why is it even stopping at all?
The $ is a red herring here. take 2 $ [1..] is precisely identical to take 2 [1..] . The $ only affects what is an argument to what; it has no effect at all on when things get evaluated.
(For example:
print 2 + 2 ==> (print 2) + 2 {- Doesn't work. -}
print $ 2 + 2 ==> print (2 + 2) {- Works. -}
The dollar affects whether print is an argument to + or the other way around. The dollar itself doesn't evaluate anything.)
The "top-most" function here is take , so we evaluate that first. The definition of take can be written like so:
take 0 xs = xs
take n xs =
case xs of
x : xs' -> x : take (n-1) xs'
[] -> []
Assuming the length isn't zero, the first thing this does is case xs of ... , which means that xs (in this case [1..] ) must be evaluated to decide whether it's a : or a [] . Doing this, we find (in constant time) that xs = 1 : [2..] , so the first case alternative applies.
You can write it out like this...
take 2 [1..]
take 2 (1 : [2..])
1 : take (2-1) [2..]
1 : take 1 [2..]
1 : take 1 (2 : [3..])
1 : 2 : take (1-1) [3..]
1 : 2 : take 0 [3..]
1 : 2 : []
(I still think it's a pity that nobody has come up with a tool to auto-generate traces like this... It could unconfuse a few people, and could be great for debugging...)
Haskell is lazy, and ($) doesn't change that. The ($) operator isn't at all magical, and it's a totally ordinary Haskell function†:
($) :: (a -> b) -> a -> b
f $ x = f x
Since Haskell is lazy, arguments are not evaluated before they are passed to a function, and ($) is no exception. Therefore, take 2 $ [1..] is identical to (take 2) [1..] , which is of course identical to take 2 [1..] . No additional evaluation takes place.
Now, as it turns out, there is a strict version of ($) called ($!) , which evaluates its argument to weak head normal form (WHNF) before applying the function. It can also be defined as an ordinary Haskell function, but it must use the magical seq function as part of its definition:
($!) :: (a -> b) -> a -> b
f $! x = x `seq` f x
However, even take 2 $! [1..] take 2 $! [1..] will produce [1,2] , not diverge. Why? Well, $! only evaluates its argument to WHNF, not normal form, and WHNF can be thought of as a “shallow” evaluation. It evaluates the first cons pair, but nothing more. You can see this by using the :sprint command in GHCi:
ghci> let xs = [1..] :: [Int]
ghci> xs `seq` ()
()
ghci> :sprint xs
xs = 1 : _
To recursively force a value, you'd need to use the deepseq package, which, as the name implies, deeply evaluates a value. It provides an even “stronger” version of ($) , called ($!!) , which is like ($!) but uses deepseq instead of seq . Therefore, take 2 $!! [1..] take 2 $!! [1..] will , in fact, diverge.
† This is not strictly true in GHC, since there are some special typing rules in the compiler to help check idiomatic uses of $ when used with higher-rank types. However, none of that is at all relevant here, and the simpler definition works identically.
To complement the other answers, let me add that you are confusing evaluation order (or evaluation strategy) and precedence. This is a frequent misconception.
To exemplify, consider the expression
f 0 * g 0 + h 0
Precedence tells us that the multiplication must be performed before the addition. However, this does not imply that f 0 and g 0 must be evaluated before h 0 ! A compiler could choose to compute h 0 first, then g 0 , then f 0 , and finally to multiply, then add.
This holds not only in Haskell, but even in imperative languages like C which do not specify an evaluation order and allow functions to have side effects.
On top of this, you also have to understand that "evaluating" something in Haskell, roughly means to evaluate it until its first constructor appears (WHNF). So, evaluating [1..] results in, roughly, 1 : [2..] where the tail has to be evaluated. If evaluating [1..] would cause an infinite loop, then there would be no way at all to use [1..] in an expression: one could only choose to discard it without evaluating it, or to loop forever.
上一篇: 更快地在Haskell中进行直方图计算
下一篇: Haskell如何在$ 1中工作？