squareOn 的文件夹 - Haskell

Question

在我的讲座中，我们必须定义函数 squareOn 使得

和 foldr。答案是

 squareOn :: (Eq a, Num a) => [a] -> a -> a        
 squareOn = foldr (\x acc y -> if y == x then x*x else acc y) id

我不明白 foldr 是如何工作的，但我是 Haskell 中 lambda 表达式的新手。 acc 是 Haskell 中的任何类型的函数吗？如果有人可以解释 squareOn 是如何工作的，那就太好了。 :)

Answer 1

让我们定义这个没有 lambda 的函数。

squareOn :: (Eq a, Num a) => [a] -> a -> a
squareOn = foldr f id
  where
    f x acc = g
      where
        g y | x == y = x * x
            | otherwise = acc y

现在变成了 foldr 平时的样子。它需要一个带有两个参数 f 和一个初始值 id.

的函数

当您将 [2, 4] 传递给 squareOn 时，它将扩展为 foldr f id [2, 4]，然后根据 foldr 的定义扩展为 f 2 (f 4 id)。

f 4 id returns 一个接受一个参数的函数 y 其中 returns 4 * 4 如果 y 是 4, returns id y 否则。我们称这个函数为 p.

p y | 4 == y = 4 * 4
    | otherwise = id y

现在，f 2 (f 4 id) returns 一个接受一个参数的函数 y 其中 returns 2 * 2 如果 y 是 2，否则 returns p y。当你命名它q时，它会像这样。

q y | 2 == y = 2 * 2
    | otherwise = p y

所以 squareOn [2, 4] 3 等同于 q 3.

Answer 2

这是 foldr 的一种高级用法。通常，我们看到 foldr 用作

fun xs = foldr (\x acc -> something using x and acc) base xs

或等同于

fun = foldr (\x acc -> something using x and acc) base

对应以下递归函数：

fun []     = base
fun (x:xs) = something using x and acc
   where acc = fun xs

您的情况是这种用法的特例，其中 base、acc 和 something using x and acc 是函数。也就是说，我们有

fun []     = \y -> base'
fun (x:xs) = \y -> something using x, acc, y
   where acc = \y -> fun xs y

回到foldr，我们得到

fun = foldr (\x acc -> \y -> something using x, acc, y) (\y -> base')

也可以写成

fun = foldr (\x acc y -> something using x, acc, y) (\y -> base')

似乎将一个令人困惑的三参数函数传递给 foldr。

您的具体情况，

squareOn = foldr (\x acc y -> if y == x then x*x else acc y) id

对应显式递归：

squareOn []     = id
squareOn (x:xs) = \y -> if y == x then x*x else acc y
   where acc = \y -> squareOn xs y

或

squareOn []     y = y
squareOn (x:xs) y = if y == x then x*x else squareOn xs y

你应该能看懂。

Answer 3

无论谁跳过这些明确的论点，都只会让你自己学习这些东西变得不必要地困难。这完全是肤浅的。添加由类型签名指定的显式参数，给我们

squareOn :: (Eq a, Num a) => [a] -> a -> a
squareOn      = foldr (\x acc y -> if y == x then x*x else acc y) id
squareOn xs   = foldr (\x acc y -> if y == x then x*x else acc y) id xs
squareOn xs y = foldr (\x acc y -> if y == x then x*x else acc y) id xs y
squareOn xs y = foldr g id xs y   where { g x acc y | y == x    = x*x 
                                                    | otherwise = acc y }
squareOn xs y = (case xs of { 
    []      -> id ;
    (x:xs2) -> g x (foldr g id xs2)
                          })  y   where { g x acc y | y == x    = x*x 
                                                    | otherwise = acc y }

现在我们可以看到这里正在发生的一切，而不是必须牢记在心。先是下棋，再就是下蒙眼棋，能看得见干嘛蒙眼下？

所以现在很明显 passing that y around^(*) 从调用到调用 unchanged 实际上在这里没有任何意义，因为它是相同的 y，并且它已经在范围内：

squareOn xs y = (case xs of { 
    []      -> y  ;
    (x:xs2) -> g x (foldr g y  xs2)
                          })      where { g x acc   | y == x    = x*x 
                                                    | otherwise = acc   }

简化为

squareOn xs y = foldr g y  xs     where { g x acc   | y == x    = x*x 
                                                    | otherwise = acc   }
{- cf.
squareOn xs y = foldr g id xs y   where { g x acc y | y == x    = x*x 
                                                    | otherwise = acc y } -}

并且像您的原始代码一样简短无意义，

squareOn      = flip (foldr g)    where { g x acc   | y == x    = x*x 
                                                    | otherwise = acc   }

或者可以简化为

squareOn xs y =  case xs of { 
    []             -> y   ;
    (x:_) | y == x -> x*x ;
    (_:xs2)        -> squareOn xs2 y }

进一步 worker/wrapper 嵌套一元工作者，以您更清楚的为准。

只有在没有嵌套范围的语言中才真正需要传递未更改的数量以使其在范围内，例如 Prolog。

^(*)_{（因此您要求的关于此技术如何工作的完整解释实际上在链接的答案中）。}

squareOn 的文件夹 - Haskell

foldr for squareOn - Haskell

function

haskell

lambda

higher-order-functions

fold