"any" 使用折叠的无点实现:为什么有些策略有效而其他策略无效?

Point-free implementation of "any" using folds: why do some strategies work and others not?

tl;博士:

这是“Haskell 从第一原则编程”中的一个练习,要求 reader 使用折叠将 any 函数重新实现为 myAny (a -> Bool) -> [a] -> Bool,并且以无点风格(如果可能)。

我被困在这个问题上并打算问一个问题,但在输入我原来的问题的过程中,我想到了以下解决方案:

myAny = curry $ foldr (||) False . uncurry map

我正在努力理解为什么 这个 有效以及我的其他尝试失败的原因。

我想指出,我确实理解 Haskell 中的所有函数都是柯里化的;我可能会松散地使用诸如“函数 x 已应用其所有参数”之类的短语。

具体来说,我的问题是:

问题 1:

为什么

myAny = foldr (||) False . map
在不使用 curry/uncurry 模式。

问题 2:

如果 curry/uncurry 模式有名称。看起来这可能与“组合器”有关,但我对它们只是模糊地熟悉。在我继续 HPFP 之旅时,其他资源会有所帮助!

问题 3:

我采取的第二个策略是将“任意”函数 f :: [a] -> Bool 放在“折叠”函数中。我得到的最远的是

myAny f = foldr ((||) . f) False

我不确定我是否可以通过此策略进一步实现无积分;我不认为有任何方法可以在参数中“通过”,这样我就可以做类似

的事情
-- This does not work; it is not syntactically valid
myAny = foldr ((||) . ) False

确实有效。我尝试了几种不同的 curry/uncurry 组合 foldr 函数和 ((.) (||)),但我似乎无法完全匹配类型。

我想了想,如果我有办法“咖喱” foldr 本身的类型签名,那么它就变成了

foldr` :: Foldable t => ((a, b) -> b) -> b -> t a -> b
foldr` f acc l = foldr (curry f) acc l

可能有一条前进的道路,但我没有成功。试图告诉 foldr“我传递给您的函数在准备就绪之前需要更多参数”似乎有一个挂断。

有没有办法使这个特定的策略起作用,或者我是否 运行 陷入了某个地方的基本限制?

问题 4

这两个问题似乎都可以归结为

There is no way to indicate that a function should not be passed to its caller until "all of its arguments are applied",

注意到,在 Haskell 和 lambda 演算中,所有函数都有一个参数。 Currying/decurrying 似乎在某些情况下可以缓解这种情况,但在其他情况下则不然。特别是,第一个策略奏效了,因为它

而第二种策略试图将部分应用的高阶函数传递给期望高阶函数(尽管阶数和类型不同)的函数,等等无法区分函数是否“准备就绪”。

这种直觉是正确的吗?是否有任何工具(无论是概念上的还是针对 Haskell 本身的)我可以用来帮助我(快速)了解我何时 运行 反对这种斗争?如果确实是我的第二个策略不会成功,我没有看到策略中的模式给我一些 a priori 指示我正在尝试做的是不可能。


长版

一些关于我自己的背景:我对函数式编程很陌生,尤其是 Haskell。我有不错的数学背景,在 python 方面有一些 imperative/object-oriented 编程经验,以及少量的一般计算机科学知识。我正在学习一些范畴论,并且对这些基础知识感到相当自在。

我正在研究“Haskell 从第一性原理编程”。到目前为止(我的版本中的第 10 章),它涵盖了 lambda 演算、类型、类型类、语法、递归、列表方法和现在的折叠的基础知识。无论是在理论上还是在实践中(通过练习),我都对这些感到相当满意。

在关于折叠的章节中,有一组练习可以通过折叠重写标准函数,并尽可能以无点的方式进行。这本书演示了许多中间版本,这些版本应该有助于收敛到使用折叠的最终无点版本。给出的示例是针对“and”函数的:

myAnd :: [Bool] -> Bool

-- VERSION 1: 
-- direct recursion, not using (&&)
myAnd [] = True
myAnd (x:xs) =
  if x == False
  then False
  else myAnd xs

-- VERSION 2
-- direct recursion, using (&&)
myAnd [] = True
myAnd (x:xs) = x && myAnd xs

-- VERSION 3:
-- fold, not point-free
-- in the folding function
myAnd = foldr
        (\a b ->
          if a == False
          then False
          else b) True

-- VERSION 4
-- fold, both myAnd and the folding
-- function are point-free now
myAnd = foldr (&&) True

我坚持的问题是对“任何”功能做同样的事情。我已经下载了前两个版本:

-- VERSION 1:
-- direct recursion
myAny :: (a -> Bool) -> [a] -> Bool
myAny f [] = False
myAny f (x:xs) =
  if f x == True
  then True
  else myAny f xs

-- Version 2:
-- direct recursion with (||)
myAny f [] = False
myAny f (x:xs) = f x || myAny f xs

但我坚持使用无积分版本。我至少看到两种策略。

首先是在 fold 函数中应用“myAny”的 a -> Bool 函数。我有三个工作版本,每个版本都更接近自由点:

myAny1 :: (a -> Bool) -> [a] -> Bool

-- All of these appear to work
myAny1 f l = foldr (\x y -> f x || y) False l
myAny1 f = foldr (\x y -> f x || y) False
myAny1 f = foldr ((||) . f) False
myAny1 = \f -> foldr ((||) . f) False

但我正在努力从上一版本的 lambda 中删除 f 参数。

由于柯里化等原因,我还不确定这是否可能。我的直觉告诉我这是不可能的;我不能简单地将 g = (.) (||) 等部分应用的函数传递给 foldr,因为参数不会从 g 中“脱落”。即,

(foldr ((.) (||)) False) f l

不是f应该先应用于“部分合成”,如((.) (||) f);上面的表达式实际上在语法上是无效的,因为 foldr 已经部分应用于两个参数并且只需要一个列表。因此,我认为该策略需要一个 lambda 项来“传递参数”并定义折叠函数,我看不出有什么方法可以避免这种情况。

在尝试了类型系统和 currying/uncurrying 之后,我有一种预感,即 foldr 的类型签名本身就是一个基本的障碍。即,它是

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b 

而不是

foldr` :: Foldable t => ((a, b) -> b) -> b -> t a -> b
foldr` f acc l = foldr (curry f) acc l

但我相当确定即使使用 foldr' 而不是 foldr 仍然阻止我成功地释放这一点——我仍然无法让 foldr“知道”,我传递给它的函数只是“部分应用”,而且我觉得没有多少 currying 或 uncurrying 可以纠正这个问题。


我的第二个策略是将函数 f 映射到列表上,然后应用 or,或者为了保持练习的精神,重新实现 or 通过折叠.

我的第一次尝试是:

-- First map `f` over `l`, then apply the fold
-- This works; makes sense so far
myAny2 f l = foldr (||) False $ map f l

我的第二次尝试是:

-- Try to eliminate the argument
-- Does not work; makes sense why
myAny2 f = foldr (||) False $ map f

不起作用,因为 map f 被用作 foldr 的最后一个参数。但是 map f 不是列表:它是一个接受列表和 returns 相同类型列表的函数。解决方法是将 $ 更改为 .:

-- Works:
myAny2 f = foldr (||) False . map f

现在,我希望能够从上述定义的两边删除 f,如

myAny2 = foldr (||) False . map

理由是 map 消耗了我们的两个参数(f 和列表);不传递它们意味着函数组合运算符 . 不被评估,因为函数应用程序的优先级高于组合。因此,当两个参数被传递给上述版本的 myAny2 时,它们首先被应用到 map、计算,然后被送入 foldr.

但是这个理解是不正确的,因为GHC会抛出如下错误:

Ch10ex.hs:28:10: error:
    • Couldn't match type ‘Bool’ with ‘[a] -> Bool’
      Expected type: (a -> Bool) -> [a] -> Bool
        Actual type: (a -> Bool) -> Bool
    • Possible cause: ‘(.)’ is applied to too many arguments
      In the expression: foldr (||) False . map
      In an equation for ‘myAny2’: myAny2 = foldr (||) False . map
    • Relevant bindings include
        myAny2 :: (a -> Bool) -> [a] -> Bool (bound at Ch10ex.hs:28:1)
   |
28 | myAny2 = foldr (||) False . map 
   |          ^^^^^^^^^^^^^^^^^^^^^^

Ch10ex.hs:28:29: error:
    • Couldn't match type ‘[Bool]’ with ‘Bool’
      Expected type: (a -> Bool) -> [a] -> Bool
        Actual type: (a -> Bool) -> [a] -> [Bool]
    • In the second argument of ‘(.)’, namely ‘map’
      In the expression: foldr (||) False . map
      In an equation for ‘myAny2’: myAny2 = foldr (||) False . map
   |
28 | myAny2 = foldr (||) False . map 
   |                             ^^^

查看类型和脱糖,我想我明白了为什么这不起作用。我们有:

map :: (a -> b) -> [a] -> [b]
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldr (||) False :: Foldable t => t Bool -> Bool
(.) :: (b -> c) -> (a -> b) -> a -> c

所以上面实际上变成了

(.) (folder (||) False) map

这意味着,在类型签名 (.) :: (b-> c) -> (a -> b) -> a -> c 中,我们必须具有 b :: t Boolc :: Boola ::... 好吧,a 不起作用。它是咖喱的,所以它不符合签名。我认为 这就是出现第一个错误的原因; “map”上的柯里化意味着只应用了一个参数,然后它尝试将函数与部分应用的 fold 函数组合起来,显然不能。我 认为 第二个错误来自试图将此类型检查传播到 map 函数;类型检查器意识到如果 map 具有类型签名 map :: (a -> Bool) -> [a] -> Bool,那么一切都可以工作(也许?)。

尽管如此,如果我们uncurry map,那么我们可以自己进行表达式类型检查:

foldr (||) False . uncurry map :: (a -> Bool, [a]) -> Bool

但这并不是 myAny 的预期类型签名。所以我们再次咖喱,一切正常:

-- Final product, working:
myAny2 = curry $ foldr (||) False . uncurry map

一切都很好。

这个curry/uncurry图案有名字吗?在实际层面上,“uncurry”完成的似乎是将“2 参数”函数 map 转换为以单个 2 元组作为参数的函数(以便它可以与一个需要“单个参数”的函数),然后重新柯里化以使给定的类型签名适合。

您的第一个示例不起作用的原因是它最终试图将 map f 作为参数传递给 foldr:

myAny = foldr (||) False . map
=
myAny f = (foldr (||) False . map) f
=
myAny f = foldr (||) False (map f)

你需要另一个层次的组合来“映射”额外的参数。我更喜欢用 fmap 来写这个来唤起那个助记符,但它等同于 (.)。 (这是使用 instance Functor ((->) x)。)

myAny = fmap (foldr (||) False) . map
=
myAny f = (fmap (foldr (||) False) . map) f
=
myAny f = fmap (foldr (||) False) (map f)
=
myAny f = foldr (||) False . map f
=
myAny f x = (foldr (||) False . map f) x
=
myAny f x = foldr (||) False (map f x)

curry/uncurry 模式并没有真正的名字,我知道,但总体策略与使用 Arrow 编程的原则有关。在这种情况下,您不是使用 fmap 来“深入”一个参数,而是使用 uncurry 将两个参数组合成一个,这样您就可以使用 (.) 制作一个线性管道,然后 curry 再次取消分组:

                                  map  ::  (a -> b) ->    [a]  -> [b]
                          uncurry map  :: ( a -> b,       [a]) -> [b]
       foldr (||) False                ::                         [Bool] -> Bool
       foldr (||) False . uncurry map  :: ( a -> Bool,    [a])           -> Bool
curry (foldr (||) False . uncurry map) ::  (a -> Bool) -> [a]            -> Bool

你可以去掉这段代码中的f

myAny f = foldr ((||) . f) False

通过重写将 f 放在可以减少 eta 的位置:

myAny f = foldr ((||) . f) False
=
myAny f = flip foldr False ((||) . f)
=
myAny f = flip foldr False ((.) (||) f)
=
myAny f = flip foldr False (fmap (||) f)
=
myAny f = (flip foldr False . fmap (||)) f
=
myAny = flip foldr False . fmap (||)

I am failing to see a pattern in the strategies that give me some a priori indication that what I am trying to do is impossible.

总是可以用无点形式编写表达式。 pointfree.io 会给你一个 不好的 无积分版本的任何东西。

如果你想要一些你不会在 public 中看到时感到尴尬的东西,那么你必须考虑数据流结构,使用像 Control.Arrow 中那样的更高级别的组合器,并且理想情况下使用许多名称清晰的中间函数。口头禅是“名称代码,而不是数据”。 pointfree 代码 (ha) 的要点是让代码更容易理解,通过 强制 你修复变量允许你编写的“意大利面条数据流”(通过让你连接任何东西到还要别的吗)。如果只是把变量名丢掉而不改进结构,结果会更难读。