如何在 Haskell 中为函数编写 Traversable 实例？

Question

如何为 ((->) a) 编写 Traversable 实例？

我想我可以做到，如果我通常可以打开一个 Applicative Functor:

instance Traversable ((->) k) where
  -- traverse :: (a -> f b) -> (k -> a) -> f (k -> b)
  -- traverse h t = ?
  -- h                     :: Applicative f => a -> f b
  -- t                     :: k -> a
  -- h . t                 :: k -> f b
  -- unwrap . h . t        :: k -> b
  -- pure $ unwrap . h . t :: f (k -> b)
  traverse h t = pure $ unwrap . h . t

unwrap :: (Functor f, Applicative f) => f a -> a
unwrap y@(pure x) = x

但是，唉，GHC 不会让我逃脱的：

Parse error in pattern: pure

Answer 1

通常没有unwrap这样的东西，考虑f是列表函子[]什么应该unwrap return for [_, _, _] 或更好的空列表 []？与 Maybe 类似，假设 h 是 const Nothing，你会期望得到 Nothing。但是，如果您尝试将 unwrap 的 Nothing 转换为值 a，您的思路就会失败。您会注意到，尝试应用 pure（将结果重新打包到仿函数中）意味着您希望结果对于 Maybe 函数始终为 Just，对于 []等

reader 仿函数 ((->) k) 的 Traversable 实例几乎没有希望。虽然这不是证据，但在这方面的一个很好的证据是 Prelude 中缺少这样的实例。此外，要遍历一个函数并生成最终容器（[] 或 Maybe），您需要将函数 h 应用于函数的任何可想到的输出，这是很多潜在的价值，一般来说无穷多。

Prelude> traverse (\n -> if n == 42 then Nothing else Just n) [1, 2, 3]
Just [1,2,3]
Prelude> traverse (\n -> if n == 42 then Nothing else Just n) [1..]
Nothing

假设k是Int，那么函子是Int ->，假设你有一个值g :: Int -> Int，让它是\n -> if n == 42 then 0 else n，假设你想用上面的函数遍历那个值，如果 g 对任何输入输出 42，那么遍历将是 Nothing，但事实并非如此。遍历无法知道这一点（它无法访问函数的代码），因此它必须尝试所有输出。

如果 k 是有限的，那么您可以通过制表来遍历函数。遍历 table 后，您可能会产生一个结果。这可能不是您想要的，但是：

import Data.Char
import Data.Maybe
import Data.Word

instance ( Enum k, Bounded k ) => Foldable ((->) k) where
    foldMap h f = foldMap (h . f) domain

instance ( Enum k, Bounded k, Eq k ) => Traversable ((->) k) where
    traverse h f = fmap (\vs k -> fromJust $ k `lookup` zip domain vs) (traverse (h . f) domain)

domain :: ( Enum k, Bounded k ) => [k]
domain = enumFromTo minBound maxBound

tabulate :: ( Enum k, Bounded k ) => (k -> a) -> [(k, a)]
tabulate f = zip domain (map f domain)

f1 :: Bool -> Int
f1 b = if b then 42 else 666

f2 :: Ordering -> Char
f2 LT = 'l'
f2 EQ = 'e'
f2 GT = 'g'

f3 :: Word8 -> Bool
f3 n = fromIntegral n < 256

f4 :: Word16 -> Bool
f4 n = fromIntegral n < 256

main = do
    print (tabulate f1)
    print (tabulate <$> traverse (\n -> [n, 2*n]) f1)
    putStrLn ""
    print (tabulate f2)
    print (tabulate <$> traverse (\c -> [c, toUpper c]) f2)
    putStrLn ""
    print (tabulate f3)
    print (tabulate <$> traverse (\b -> if b then Just b else Nothing) f3)
    putStrLn ""
    print (tabulate <$> traverse (\b -> if b then Just b else Nothing) f4)

Answer 2

But, alas, GHC won't let me get away with that:

您的错误似乎是您试图将函数 (pure) 用作模式。 Haskell 只允许 构造函数 出现在模式中。所以

unwrap (Just x) = x

有效，而

unwrap (pure x) = x

不是。

如何在 Haskell 中为函数编写 Traversable 实例？

How to write a Traversable instance for function, in Haskell?

haskell

traversable