Тестирование обходимости Haskell на простом примере

Я пытаюсь обойти все элементы структуры данных в haskell, используя Data.Traversable, который задокументирован по следующим URL-адресам:

http://hackage.haskell.org/package/base-4.6.0.1/docs/Data-Traversable.html http://www.haskell.org/haskellwiki/Foldable_and_Traversable

До сих пор я придумал следующий код, в котором, насколько я знаю, отсутствует правильная реализация экземпляра Tr.Traversable.

import qualified Data.Traversable as Tr
import qualified Data.Foldable as Fl
import Control.Monad
import Control.Applicative

data Test = Test { desc  :: String
                 , value :: Int
} 

data Data t = Data { foo :: t 
                   , bar :: t       
} 

exampleData = Data { foo = Test "Foo" 1 
                   , bar = Test "Bar" 2
}

instance Show Test where
  show f = (desc f) ++ ": " ++ (show $ value f)

instance (Show a) => Show (Data a) where
  show f = show (foo f)

instance Functor Data where
  fmap = Tr.fmapDefault

instance Fl.Foldable Data where
  foldMap = Tr.foldMapDefault

instance Tr.Traversable Data where
    traverse f = Data f  -- Try to show a Test entry inside the Data structure

--  
--  traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
--

main = do
  putStrLn $ show exampleData
  Tr.traverse (putStrLn show) exampleData

Я пытаюсь распечатать все элементы в exampleData, член за членом и используя show. Я на правильном пути и как реализовать обходной экземпляр?


haskell functor traversable
person toeplitz    schedule 24.01.2014    source источник

Ответы (3)


arrow_upward
5
arrow_downward

Я бы просто использовал расширения языка, чтобы получить его для меня:

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE DeriveFoldable #-}
import qualified Data.Traversable as Tr
import qualified Data.Foldable as Fl
import Control.Monad
import Control.Applicative

data Test = Test { desc  :: String
                 , value :: Int }

data Data t = Data { foo :: t
                   , bar :: t } deriving (Functor, Tr.Traversable, Fl.Foldable)

exampleData = Data { foo = Test "Foo" 1
                   , bar = Test "Bar" 2
}

instance Show Test where
  show f = (desc f) ++ ": " ++ (show $ value f)

instance (Show a) => Show (Data a) where
  show f = show (foo f)

main = do
  putStrLn $ show exampleData
  Tr.traverse (putStrLn . show) exampleData

> runhaskell test_traversable.hs
Foo: 1
Foo: 1
Bar: 2
()

Если вы хотите знать, как компилятор автоматически реализует это, вы можете скомпилировать его с флагом -ddump-deriv (немного очистив):

instance Functor Data where
  fmap f (Data foo' bar') = Data (f foo') (f bar')

instance Tr.Traversable Data where
  tr.traverse f (Data foo' bar') = Data <$> (f foo') <*> (f bar')

instance Fl.Foldable Data where
  Fl.foldr f z (Data foo' bar') = f foo' (f bar' z)
person bheklilr    schedule 24.01.2014
comment
Спасибо, это решает проблему при добавлении новых участников, как я и спрашивал в комментариях под ответом @rampion. - person toeplitz; 25.01.2014

arrow_upward
3
arrow_downward

Типичная реализация Traversable здесь будет такой:

traverse f (Data foo bar) = Data <$> f foo <*> f bar
person Louis Wasserman    schedule 24.01.2014

arrow_upward
3
arrow_downward

Таким образом, ваше определение traverse не унифицируется с данной подписью.

traverse f = Data f -- f :: x implies Data f :: x -> Data x, so this implies
traverse :: x -> x -> Data x

тогда как если бы Data был экземпляром Traversable, то мы бы специализировали Tr.traverse на

Tr.traverse :: Applicative f => (a -> f b) -> Data a -> f (Data b)

Попытка их унифицировать дает проблемы:

traverse ~ Tr.traverse if and only if
  x ~ (a -> f b)
  x ~ Data a
  Data x ~ f (Data b)

Вот почему компилятор жалуется:

Couldn't match expected type `Data a' with actual type `a -> f b'
In the first argument of `Data', namely `f'
In the expression: Data f
In an equation for `traverse': traverse f = Data f

Итак, давайте дадим правильное определение для траверса:

traverse f (Data a a') = Data <$> f a <*> f a'

Далее у вас есть ошибка в вашей основной функции. Вы написали Tr.traverse (putStrLn show) exampleData, когда имели в виду Tr.traverse (putStrLn . show) exampleData.

putStrLn относится к типу String -> IO (), поэтому putStrLn show необходимо, чтобы show было строкой для проверки типов, но show :: Show a -> a -> String. Вот почему компилятор жалуется:

Couldn't match expected type `Test -> IO b0'
            with actual type `IO ()'
In the return type of a call of `putStrLn'
Probable cause: `putStrLn' is applied to too many arguments
In the first argument of `Tr.traverse', namely `(putStrLn show)'
In a stmt of a 'do' block: Tr.traverse (putStrLn show) exampleData

Couldn't match type `a0 -> String' with `[Char]'
Expected type: String
  Actual type: a0 -> String
In the first argument of `putStrLn', namely `show'
In the first argument of `Tr.traverse', namely `(putStrLn show)'
In a stmt of a 'do' block: Tr.traverse (putStrLn show) exampleData

Вы хотели составить эти функции с помощью оператора .:

putStrLn . show == \a -> putStrLn (show a)

Вы также можете просто использовать print, который определяется как putStrLn . show.

person rampion    schedule 24.01.2014
comment
Спасибо за хороший ответ. Можно ли еще больше обобщить это, чтобы я мог добавлять элементы в структуру данных без добавления аргументов в функцию обхода? Теперь это поддерживает только два члена в этом примере. - person toeplitz; 25.01.2014