delete
是一种模态搜索。它有两种不同的操作模式 - 是否已经找到结果。您可以使用foldr
构造一个函数,将状态作为每个元素被检查时向下传递。因此,在delete
的情况下,状态可以是一个简单的Bool
。虽然它不是最好的类型,但愿意依旧可行。
一旦确定了状态类型,就可以开始对foldr
进行构建。我将按照我自己的方式来解释如何完成这个过程。为了更好地注释子表达式的类型,我将启用ScopedTypeVariables
。一旦你知道状态类型,你就知道你想要foldr
生成一个接受该类型值并返回所需终类型值的函数。这就足够开始草图了。
{-# LANGUAGE ScopedTypeVariables #-}
delete :: forall a. Eq a => a -> [a] -> [a]
delete a xs = foldr f undefined xs undefined
where
f :: a -> (Bool -> [a]) -> (Bool -> [a])
f x g = undefined
这只是一个开始。g
的确切含义有点棘手。实际上,它是处理列表其余部分的函数。事实上,把它看作是一个续集是准确的。它绝对代表执行剩下的折叠,带着你选择传递的任何状态。鉴于此,现在是时候想出在某些 undefined
位置放什么了。
{-# LANGUAGE ScopedTypeVariables #-}
delete :: forall a. Eq a => a -> [a] -> [a]
delete a xs = foldr f undefined xs undefined
where
f :: a -> (Bool -> [a]) -> (Bool -> [a])
f x g found | x == a && not found = g True
| otherwise = x : g found
看起来相对简单。如果当前元素是要搜索的元素,并且它尚未被找到,则不输出它,并继续将状态设置为True
,表示已经找到。否则,输出当前值并继续使用当前状态。这只是让 foldr
的其余参数留下来。最后一个参数是初始状态。另一个参数是空列表的状态函数。好吧,这些也不算太难。
{-# LANGUAGE ScopedTypeVariables #-}
delete :: forall a. Eq a => a -> [a] -> [a]
delete a xs = foldr f (const []) xs False
where
f :: a -> (Bool -> [a]) -> (Bool -> [a])
f x g found | x == a && not found = g True
| otherwise = x : g found
无论状态如何,遇到空列表时都要生成一个空列表。初始状态是尚未找到正在搜索的元素。
这种技术在其他情况下也适用。例如,可以将
foldl
写成这种方式的
foldr
。如果您把
foldl
看作是一个反复转换初始累加器的函数,那么可以猜测出它所生产的函数——如何转换初始值。
{-# LANGUAGE ScopedTypeVariables #-}
foldl :: forall a b. (a -> b -> a) -> a -> [b] -> a
foldl f z xs = foldr g id xs z
where
g :: b -> (a -> a) -> (a -> a)
g x cont acc = undefined
基本情况并不太难找出,当问题定义为操作名为
z
的初始累加器时。空列表是恒等变换
id
,传递给创建的函数的值是
z
。
实现
g
更加棘手。它不能只是盲目地根据类型完成,因为有两个不同的实现使用了所有预期值和类型检查。这是一种情况,类型不足以解决问题,需要考虑可用函数的含义。
让我们从似乎应该使用的值及其类型的清单开始。看起来必须在
g
的主体中使用的内容是
f :: a -> b -> a
、
x :: b
、
cont :: (a -> a)
和
acc :: a
。显然,
f
将把
x
作为其第二个参数,但关键问题是在哪里使用
cont
。为了找出它应该放置的位置,请记住它代表通过处理剩余列表返回的转换函数,并且
foldl
在处理当前元素后将该处理的结果传递给剩余部分的列表。
{-# LANGUAGE ScopedTypeVariables #-}
foldl :: forall a b. (a -> b -> a) -> a -> [b] -> a
foldl f z xs = foldr g id xs z
where
g :: b -> (a -> a) -> (a -> a)
g x cont acc = cont $ f acc x
这也表明
foldl'
只需进行微小更改就可以这样编写:
{-# LANGUAGE ScopedTypeVariables #-}
foldl' :: forall a b. (a -> b -> a) -> a -> [b] -> a
foldl' f z xs = foldr g id xs z
where
g :: b -> (a -> a) -> (a -> a)
g x cont acc = cont $! f acc x
区别在于
($!)
用于建议在将
f acc x
传递给
cont
之前对其进行求值。(我说“建议”是因为有一些边缘情况,其中
($!)
甚至不会强制执行到WHNF。)