这个函数能以“点无形式”写出吗？如果不能，为什么？

Question

这个函数能以“点无形式”写出吗？如果不能，为什么？

13

一个相关的问题是这个，但是有些回答说几乎任何东西都可以变成无点函数，那么这个函数有什么问题？

\[x] -> x

http://pointfree.io/似乎不能用点分式风格写。这是意味着它无法以那种方式书写吗？如果是这样，那么理论上的原因是什么？

我只能观察到上面的函数是head（或last）的“残缺”版本，它只能操作单例列表。确实，在非单例列表上应用它时，它会在ghci中出现错误：

*** Exception: <interactive>:380:5-13: Non-exhaustive patterns in lambda

也许模式上的“非穷尽性”是一些函数无法以无点样式编写的原因？

根据答案进行编辑：

没想到我的问题的答案会如此复杂（事实上，我只是认为简短的答案应该是“不行”，），所以我需要花些时间仔细阅读它们、稍微试验一下，并理解它们，否则我不能决定哪个应该被接受。暂时给Jon Purdy的答案加上+1，我可以轻松地理解其中的这就是我在普通代码中停止的地方。

- Enlico

“head”基本上会取消元素的包装，但对于具有两个或更多元素的列表不会引发错误。 - Willem Van Onsem

通常情况下，only 函数可以解决问题：https://hackage.haskell.org/package/ghc-8.10.1/docs/Util.html#v:only 但是在非调试模式下，为了提高性能，它等同于 head 函数。 - Willem Van Onsem

3个回答

9

当然，几乎任何东西都可以使用 pointfree 编程方式实现。麻烦的是，在结果表达式中允许哪些函数。如果我们进行模式匹配，则通常需要一个折叠函数来执行匹配。例如，如果我们对 Maybe a 进行模式匹配，我们需要用 maybe 替换它。同样，Either a b 模式可以使用 either 来表示。

请注意签名中的模式。

data Maybe a = Nothing | Just a

maybe :: b -> (a -> b) -> (Maybe a -> b)

Maybe可能有两个构造函数，一个不带参数，另一个带有一个a参数。所以maybe需要两个参数：一个是0元函数(b)，另一个带有a类型的参数(a -> b)，然后返回一个从Maybe a -> b的函数。同样的模式也存在于either中。

data Either a b = Left a | Right b

either :: (a -> c) -> (b -> c) -> (Either a b -> c)

两种情况。第一种情况接受一个 a 并产生我们想要的任何 c。第二种情况接受一个 b 并产生我们想要的任何 c。在每种情况下，我们希望有一个函数来处理和类型中的每个可能项。

为了系统地将像 \[x] -> x 这样的函数无点风格化，我们需要类似的折叠功能。[a] 被声明为基本上是......

data [a] = [] | a : [a]

因此，我们需要一个具有这个签名的函数。

list :: b -> (a -> [a] -> b) -> ([a] -> b)

现在，flip foldr函数接近于

flip foldr :: b -> (a -> b -> b) -> ([a] -> b)

但它是递归的。它在 a : [a] 的 [a] 部分上调用了提供的函数。我们需要一个真正的折叠函数，这在Haskell的基本库中并没有提供。一个快速的Hoogle搜索告诉我们，这个函数确实存在于一个包中，叫做 extra。当然，对于这个小例子，我们可以非常容易地自己编写它。

list :: b -> (a -> [a] -> b) -> ([a] -> b)
list f g x = case x of
               [] -> f
               (y:ys) -> g y ys

现在我们可以轻松地将它应用到你的\[x] -> x中。首先，让我们写出你的函数实际执行的内容，包括所有混乱的undefined情况（为了简洁起见，我将使用undefined而不是长错误消息）。

func :: [a] -> a
func x = case x of
           [] -> undefined
           (y:ys) -> case ys of
                       [] -> y
                       (_:_) -> undefined

现在每个case语句都恰好匹配一个构造函数。这很适合转换成折叠。

func :: [a] -> a
func x = case x of
         [] -> undefined
         (y:ys) -> list y undefined ys

现在我们也要改变外壳

func :: [a] -> a
func x = list undefined (\y -> list y undefined) x

所以我们有：

func :: [a] -> a
func = list undefined (\y -> list y undefined)

或者，如果我们想真正疯狂一些

func :: [a] -> a
func = list undefined (flip list undefined)

但是这个函数不在基本库中

是的，这是真的。我们有点作弊，使用了一个不存在的fold函数。如果我们想系统地做到这一点，我们需要那个fold操作符。但是即使没有它，我们仍然可以用foldr1来凑合，这足以满足我们特定的目的。

func' :: [a] -> a
func' = foldr1 (const (const undefined))

因此，回答你的问题，在没有合适签名的折叠函数的情况下，我们不能总是像在你的例子中那样系统地替换模式匹配成为点自由风格编程范式。幸运的是，这个函数总是可以编写出来，针对任何Haskell 98数据类型（可能也包括GADTs，但我还没有深入考虑过这种可能性）。但即使没有这种支持，我们仍然可以让它正常工作，某种程度上。

- Silvio Mayolo

1

+1，我现在才有时间阅读您的答案；我花了一点时间才通过您将case更改为list的部分，因为有一个拼写错误，我刚刚已经修正了它。 - Enlico

关于答案最简单的部分，即最后一部分，“func”通过以其第一个元素作为累加器来折叠输入列表，但是如果二元函数“const.const undefined”被应用，则会立即失败，因为该函数忽略了两个参数并返回“undefined”。非常好！ - Enlico

似乎很清楚maybe就像一个fold函数，因为它需要一个累加器和一个要应用于Maybe内部内容的函数。然而，以同样的方式看待either并不容易。无论如何，这似乎更像是一个更一般化的fold而不是实际的fold，因为我们没有折叠一个Foldable，对吧？你知道哪里可以找到更多关于这个有趣观点的好地方吗（这对我来说看起来很像可爱的理论东西）？好吧，HTNW在他的回答开头似乎确切地提到了这些东西。 - Enlico

你可能会对我提出的另一个问题感兴趣，可以考虑回答一下。 - Enlico

你说得没错。在 Haskell 中，Functor、Applicative 和 Monad 的序列严格基于相应的数学概念，而 Foldable 更像是一种松散的实用类型类，没有确切的对应数学定义。我在这里使用的“fold”概念是数学家所谓的 F-代数的 catamorphism。你提供一个 F-代数（其中 F=Either），它就会生成到你的代数的唯一 catamorphism。 - Silvio Mayolo

维基百科上有所有这些术语的正式定义，但当我最初学习这些东西时，这篇论文(https://maartenfokkinga.github.io/utwente/mmf91m.pdf) 在理解实用方面非常有价值。而那篇论文中的概念已经被实现在了一个 Haskell 库(https://hackage.haskell.org/package/recursion-schemes) 中，虽然对于真实项目来说过于冗长，但在教育使用中非常方便。 - Silvio Mayolo

6

用pointfree形式编写这个代码的简单方法是使用fold，其中累加器状态是以下之一：

- 空：我们还没有看到任何元素；保留它 - 满：我们已经看到一个元素；引发错误

如果最终状态为“空”，我们也会引发错误。这个累加器可以用Maybe自然表示：

fromSingleton :: (Foldable t) => t a -> a
fromSingleton
  = fromMaybe (error "empty list")
  . foldr (flip maybe (error "plural list") . Just) Nothing

在普通代码中，我会在这里停下来。但是...

如果您不想使用辅助数据类型，可以通过使用Böhm-Berarducci编码将 Maybe 标记消除：

type Maybe' r a
  = r          -- ‘Nothing’ continuation
  -> (a -> r)  -- ‘Just’ continuation
  -> r         -- Result

just' :: a -> Maybe' r a
-- just' = \ x _n j -> j x
just'
  = const     -- Ignore ‘Nothing’ continuation
  . flip ($)  -- Apply ‘Just’ continuation to value

nothing' :: Maybe' r a
-- nothing' = \ n _j -> n
nothing' = const  -- Ignore ‘Just’ continuation

maybe' :: r -> (a -> r) -> Maybe' r a -> r
-- maybe' = \ n j k -> k n j
maybe'
  = flip      -- Apply to ‘Just’ continuation
  . flip ($)  -- Apply to ‘Nothing’ continuation

fromMaybe' :: r -> Maybe' r r -> r
-- fromMaybe' = \ n k -> k n id
fromMaybe' = flip maybe' id  -- Pass ‘id’ as ‘Just’ continuation

然而，我们不能只是将Just替换为just'，maybe替换为maybe'等等，因为类型不匹配：

> :t fromMaybe' (error "empty list") . foldr (flip maybe' (error "plural list") . just') nothing'

<interactive>:…:…: error:
    • Occurs check: cannot construct the infinite type: c ~ Maybe' c c
      Expected type: c -> Maybe' c c -> Maybe' c c
        Actual type: c -> Maybe' (Maybe' c c) c -> Maybe' c c
    • In the first argument of ‘foldr’, namely
        ‘(flip maybe' (error "plural list") . just')’
      In the second argument of ‘(.)’, namely
        ‘foldr (flip maybe' (error "plural list") . just') nothing'’
      In the expression:
        fromMaybe' (error "empty list")
          . foldr (flip maybe' (error "plural list") . just') nothing'

问题在于我们从一个 Maybe' 的继续函数返回了一个 Maybe'，而编译器正试图统一这两种结果类型。一个解决方案是先进行 eta 扩展以让类型检查器知道我们想要构造一个不同的函数：

> :t fromMaybe' (error "empty list") . foldr (\ x acc -> \ n j -> maybe' (just' x n j) (error "plural list") acc) nothing'

fromMaybe' (error "empty list") . foldr (\ x acc -> \ n j -> maybe' (just' x n j) (error "plural list") acc) nothing'
  :: Foldable t => t c -> c

接下来，我们可以逐步重写为点式形式：

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (\ x acc
      -> \ n j
        -> maybe'
          (just' x n j)
          (error "plural list")
          acc)
    nothing'

-- Move ‘n’ & ‘j’ past ‘error …’ with ‘flip’:

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (\ x acc
      -> \ n j
        -> flip maybe'
           ----
          (error "plural list")
          (just' x n j)
          acc)
    nothing'

-- Move ‘n’ & ‘j’ past ‘acc’ with ‘flip’ again:

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (\ x acc
      -> \ n j
        -> flip (flip maybe' (error "plural list")) acc
           ----
          (just' x n j))
    nothing'

-- Eta-reduce ‘j’ with composition:

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (\ x acc
      -> \ n
        -> flip (flip maybe' (error "plural list")) acc
          . just' x n)
          --
    nothing'

-- Eta-reduce ‘n’ with ‘fmap’ (to map “under” an argument):

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (\ x acc
      -> fmap (flip (flip maybe' (error "plural list")) acc)
         ----
        . just' x)
    nothing'

-- Move ‘x’ rightward with ‘flip’ on the outside:

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (flip (\ acc x
     ----
      -> fmap (flip (flip maybe' (error "plural list")) acc)
        . just' x))
    nothing'

-- Replace composition with ‘fmap’:

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (flip (\ acc x
      -> fmap (fmap (flip (flip maybe' (error "plural list")) acc))
         ----
        (just' x)))
    nothing'

-- Eta-reduce ‘x’ with composition:

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (flip (\ acc
      -> fmap (fmap (flip (flip maybe' (error "plural list")) acc))
        . just'))
        --
    nothing'

-- Replace composition with ‘fmap’:

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (flip (\ acc
      -> fmap (fmap (fmap (flip (flip maybe' (error "plural list")) acc)))
         ----
        just'))
    nothing'

-- Move ‘acc’ rightward with ‘flip’:

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (flip (\ acc
      -> flip fmap just'
         ----
        (fmap (fmap (flip (flip maybe' (error "plural list")) acc)))))
    nothing'

-- Eta-reduce with composition:

fromSingleton
  = fromMaybe' (error "empty list")
  . foldr
    (flip
      (flip fmap just'
        . fmap . fmap . flip (flip maybe' (error "plural list"))))
        --     -      -
    nothing'

这段代码也可以完全使用 pointfree（比起 pointfree 生成的代码稍微难读，但是比我们原本的代码要好）。实际上，在 pointfree 代码中使用许多小的辅助定义（如 fromMaybe'）而不是将所有内容内联是一种良好的实践，但我们可以继续内联它们的定义。



然而，你不能轻率地内联它们并获得完全相同的类型 - 如果这样做，你会得到 (可折叠 t) => t (a -> b) -> a -> b。通过仔细思考并重新编写来进行 eta 扩展，从而获得预期的类型 (可折叠 t) => t a -> a，这可能是一个很好的练习。

- Jon Purdy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- HTNW · Accepted Answer

好的，数据类型并不是一个函数。只要你的函数没有解包任何数据值（即它只是在函数/构造函数之间移动它们），你就可以写成点自由形式，但是没有点自由匹配的语法。然而，每种数据类型只需要一个非点自由函数：折叠。在Haskell中，数据类型基本上是通过它们的折叠来定义的。使用相关数据类型的折叠作为原语，您可以重写任何函数为点自由形式。请注意，实际上有几个可能的“折叠”方式。对于[a]，递归的方式（来自Church/Böhm-Berarducci编码）是foldr :: (a -> b -> b) -> b -> [a] -> b。另一种可能的折叠方式是“case-but-it's-a-function”，(a -> [a] -> b) -> b -> [a] -> b，它来自Scott编码（然后可以使用fix恢复递归，这是另一个“点实点自由原语”），但是，正如@SilvioMayolo指出的那样，在标准库中没有这样的函数。任何一种都可以，但我们没有预定义后者，所以让我们只使用foldr。

\[x] -> x

可以编写

fst . foldr (\x f -> (snd f x, \_ -> error "got (_ : _ : _) wanted [x]")) (error "got [] wanted [x]", id)
-- I don't care enough to replicate the exact exceptions.
-- this is "flattened" from
let fold [] = (error "got [] wanted [x]", id)
    fold (x : xs) = (snd (fold xs) x, \_ -> error "got (_ : _ : _) wanted [x]")
in  fst . fold

fold 函数返回一对值，基本上是 (如果这是整个列表要返回的内容，如果不是则如何转换头部)。对于[]，如果这是整个列表，则希望返回错误，否则将在我们遇到[]之前右侧的元素传递过去。对于x：xs，如果有一个元素在它之前，我们希望忽略它并返回错误，如果没有，则要将它传递给snd（fold xs），该函数检查是否xs = []或者返回错误。我们已经消除了所有匹配项，所以只需通过 pointfree.io 将此推送到参数中的foldr 的\x f -> _中：

behead = fst . foldr (flip flip (const (error "got (_ : _ : _) wanted [x]")) . ((,) .) . flip snd) (error "got [] wanted [x]", id)
ghci> :t behead
behead :: Foldable t => t c -> c
ghci> behead []
*** Exception: got [] wanted [x]
ghci> behead [1]
1
ghci> behead [1, 2]
*** Exception: got (_ : _ : _) wanted [x]
ghci> behead [1..]
*** Exception: got (_ : _ : _) wanted [x]

很可爱。

注意：之前的版本使用了“内联”辅助数据类型，基本上是因为我在写作时想到了它。但是，它无法正确处理无限列表（behead [1..] 会挂起）。这个版本使用内置的对偶作为辅助数据类型，它们具有足够的库支持，使我不必将它们内联以使其点自由。稍微难一些的是内联(,)，从而消除fst和snd的实现中的点性，但这仍然是可能的，使用这个新类型：

newtype Pair a b = Pair { unPair :: forall r. (a -> b -> r) -> r }

或者，稍微欺骗一下类型，使用这个：

-- residual pointfullness can be reduced by pointfree.io
\xs -> foldr (\x r f -> f (r (const id) x) (\_ -> error "got (_ : _ : _) wanted [x]")) (\f -> f (error "got [] wanted [x]") id) xs (\x _ _ -> x) undefined