Как написать экземпляр Traversable для функции, в Haskell?

Question

Как мне написать экземпляр 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

Answer 1

Обычно такой вещи как unwrap, рассматривать f быть функтором списка [] что должно unwrap вернуться за [_, _, _] или еще лучше за пустой список []? Аналогичная вещь с Maybeпредположим h является const Nothing, вы ожидаете получить Nothing, Но ваша линия мысли потерпит неудачу при попытке unwrap Nothing в значение a, Вы можете заметить, что пытаясь применить pure (переупаковка результата в функтор) означает, что вы ожидаете, что результат будет всегда Just за Maybe функтор, не пустой для [] и т.п.

Существует мало надежды на Traversable экземпляр для читателя функтора ((->) 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)

Answer 2

Но, увы, GHC не даст мне сойти с рук:

Кажется, ваша ошибка в том, что вы пытались использовать функцию (pure) как шаблон. Haskell позволяет конструкторам появляться только в шаблонах. Так

unwrap (Just x) = x

действует, пока

unwrap (pure x) = x

не является.