这个函数可以写成无点风格吗？如果不是，为什么？

Question

一个相关的问题是this，但有些答案说几乎任何东西都可以免费点，那么这个功能有什么问题呢？

\[x] -> x

http://pointfree.io/似乎无法以无点风格编写它。这是否意味着它不能这样写？如果是这样，它的理论原因是什么？

我只能观察到上面的函数是head（或last，fwiw）的“残缺”版本，它只能在单例列表上运行。实际上，应用于非单例列表时，它会以这种方式出错ghci：

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

也许模式上的“非穷尽性”是某些函数不能以无点风格编写的原因？

根据答案编辑：

我没想到我的问题的答案会如此复杂（我觉得我只是认为简短的答案是否定的，实际上不可能），所以我需要找一些时间仔细阅读它们，尝试一下，然后全神贯注于它们，否则我无法决定应该接受哪一个。目前，对 Jon Purdy 的回答 +1，我可以很容易地理解这是我将在普通代码中停下的地方。

Answer 1

好吧，数据类型不是函数。只要您的函数没有解开任何数据值（即它只是在函数/构造函数之间对它们进行混洗），您就可以将其编写为无点，但根本没有用于无点匹配的语法。但是，对于每种数据类型，您只需要一个非点自由函数：折叠。在 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，fix，这是另一个“pointful pointfree原语”），但是，正如@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返回一对，基本上(what to return if this was the entire list, how to transform the head if it wasn't)。对于[]，如果那是整个列表，我们想要返回一个错误，否则在我们点击之前传递元素[]。For x : xs，如果它前面有一个元素，我们想忽略它并返回一个错误，如果没有，我们想把它传递给snd (fold xs)，它检查是否xs = []给出错误。我们已经消除了所有匹配项，因此只需通过 pointfree.io 将其推送到\x f -> _参数中即可foldr：

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..]会挂起）。这个版本使用内置对作为辅助数据类型，它有足够的库支持，我不必内联它们以使其成为无点。这稍硬是内联(,)，从而消除的实现内部pointfullnessfst和snd，但它仍然是可能的，使用这种NEWTYPE：

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

Answer 2

当然，几乎任何东西都可以成为pointfree。棘手的是您将允许在结果表达式中使用哪些函数。如果我们进行模式匹配，我们通常需要一个 fold 函数来进行匹配。因此，例如，如果我们在 a 上进行模式匹配Maybe a，我们需要将其替换为maybe。类似地，Either a b模式可以写成either。

注意签名中的模式

data Maybe a = Nothing | Just a

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

Maybe a有两个构造函数，一个不带参数，另一个带a. Somaybe需要两个参数：一个是 0-ary 函数 ( 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我们想要的任何东西。第二个接受 ab并产生c我们想要的任何东西。在每种情况下，我们都希望 sum 类型中的每个可能项都有一个函数。

为了系统地指向一个像 的函数\[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)

但是这个功能不在基础中

对，那是真的。我们通过使用不存在的折叠来欺骗。如果我们想系统地做到这一点，我们需要折叠运算符。但是没有它，我们仍然可以将它与 混合在一起foldr1，这足以满足我们的特定目的。

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

所以，为了回答你的问题，我们不能总是像你的例子那样系统地用 pointfree 替换模式匹配，除非我们有一个带有正确签名的折叠函数。幸运的是，对于任何 Haskell 98 数据类型（也可能是 GADT，但我没有深入考虑这种可能性），始终可以编写该函数。但即使没有这种支持，我们仍然可以让它发挥作用。

Answer 3

以无点形式编写此代码的一种简单方法是使用折叠，其中累加器状态是以下之一：

• Empty：我们还没有看到一个元素；收下

• Full：我们看到了一个元素；引发错误

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

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

这是我将在普通代码中停止的地方。但…

如果您不想使用辅助数据类型，可以Maybe通过使用 Böhm–Berarducci 编码来表示它来摆脱：

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

但是，我们不能只对Justwith just'、maybewith 等进行批量替换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'延续中返回 a ，而编译器试图统一这两种结果类型。一个解决方案是首先 eta-expand 让类型检查器知道我们想要在哪里构造一个不同的函数：

> :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

然后我们可以增量地重写为 pointfree 形式：

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 代码中使用许多小的辅助定义fromMaybe'而不是内联所有内容是一种很好的做法，但是我们可以继续内联它们的定义。

但是，您不能天真地内联它们并获得完全相同的类型 - 如果这样做，您将到达(Foldable t) => t (a -> b) -> a -> b. 在需要进行 eta 扩展和重写以获得预期类型的​​地方，这可能是一个很好的练习(Foldable t) => t a -> a。