haskell 表达式评估

Question

我是 haskell 的新手，我希望你能给我关于以下 haskell 表达式评估的建议。

f xs = foldr (\x n->n+1) 0 xs

函数

f [1, 4]

评价

(\x n->n+1) 1 (foldr  (\x n->n+1) 0 [4])
= (foldr  (\x n->n+1) 0 [4]) + 1
= ((\x n->n+1) 4 (foldr  (\x n->n+1) 0 [4])) + 1
= (foldr  (\x n->n+1) 0 [] + 1) + 1
= (0 + 1) + 1 
= 1 + 1
= 2

Answer 1

首先我们需要 foldr 实现：

foldr f z []     = z 
foldr f z (x:xs) = f x (foldr f z xs)

现在让我们尝试 "trace" 我们的计算 f [1, 4]:

f [1, 4]  -- rewrite list 
f (1:(4:[]))  -- replace f function where xs = (1:(4:[]))
foldr (\x n-> (+) n 1 ) 0 (1:(4:[])) 

-- using foldr f z (x:xs) = f x (foldr f z xs)
-- where f = (\x n -> (+) n 1), z = 0, x = 1, xs = (4:[])
(\x n ->(+) n 1) 1 ( foldr (\x n -> (+) n 1) 0 (4:[]))

-- lambda function will be evaluated with x = 1, n = ( foldr (\x n -> n+1) 0 (4:[]))
(+) (foldr (\x n -> n+1) 0 (4:[])) 1

-- (+) will try to evaluate first parameter
-- foldr will be applied with f = (\x n -> (+) n 1), z = 0,  x = 4, xs = []
(+) ((\x n -> (+) n 1) 4 (foldr (\x n -> (+) n 1) 0 [] )) 1

-- now again the lambda will be evaluated where x = 4 and n = (foldr (\x n -> (+) n 1) 0 [] )

(+) ( (+) (foldr (\x n -> (+) n 1) 0 [] ) 1 ) 1

--  now foldr will be evaluated again but this time first form will be used, so just z counts: f = (\x n -> (+) n 1), z = 0, [] = []
(+) ( (+) ( 0 ) 1 ) 1

-- now just go with the flow
(+) ( (+) 0 1 ) 1
(+) ( 1 ) 1
(+) 1 1
2