1

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

我想我可以做到，如果我可以一般地打开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
4

2 回答 2

6

通常没有这样的事情unwrap，考虑f成为列表函子[]应该为空列表unwrap返回什么或更好？类似的事情，假设是，你会期望得到。但是你的思路会在尝试进入value时失败。您会注意到尝试应用（将结果重新打包到函子中）意味着您希望结果始终为函子，非空等。[_, _, _][]Maybehconst NothingNothingunwrapNothingapureJustMaybe[]

Traversable例如 reader functor几乎没有希望((->) k)。虽然这不是证据，但在这个方向上的一个很好的证据是这样的实例在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，假设你想用上面的函数遍历那个值，那么遍历将是Nothing如果g输出42任何输入，但它没有。遍历无法知道这一点（它无法访问函数的代码），因此它必须尝试所有输出。

如果k是有限的，那么你可以通过列表来遍历一个函数。遍历表后，您可能会产生结果。这可能不是您所追求的，但是：

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)
于 2017-09-20T21:54:14.207 回答
1

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

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

unwrap (Just x) = x

是有效的，而

unwrap (pure x) = x

不是。

于 2017-09-23T03:08:58.477 回答