Что не так с моей (попыткой) реализации iterateM? - PullRequest
Новая
       0

Что не так с моей (попыткой) реализации iterateM?

6 голосов
/ 03 октября 2011

Я хотел бы реализовать функцию iterateM, тип которой будет выглядеть следующим образом: 

iterateM :: Monad m => (a -> m a) -> a -> [m a]

Тем не менее, мой первый шаг в написании этой функции: 

iterateM f x = f x >>= (\x' -> return x' : iterateM f x')

Дает мнеошибка: 

Could not deduce (m ~ [])
from the context (Monad m)
  bound by the type signature for
             iterateM :: Monad m => (a -> m a) -> a -> [m a]
  at main.hs:3:1-57
  `m' is a rigid type variable bound by
      the type signature for
        iterateM :: Monad m => (a -> m a) -> a -> [m a]
      at main.hs:3:1
Expected type: [a]
  Actual type: m a
In the return type of a call of `f'
In the first argument of `(>>=)', namely `f x'
In the expression: f x >>= (\ x' -> return x' : iterateM f x')

Если я удаляю свою подпись типа, ghci сообщает мне, что тип моей функции: 

iterateM :: Monad m => (a -> [a]) -> a -> [m a]

Чего мне здесь не хватает?

Ответы [ 2 ]

12 голосов
/ 03 октября 2011

Что я собираю из вашей подписи: 

iterateM :: (Monad m) => (a -> m a) -> a -> [m a]

Это то, что n-й элемент iterateM f x будет действием, которое выполняется f n раз. Это очень близко к iterate, я подозреваю, что мы можем реализовать это с точки зрения этого. 

iterate :: (b -> b) -> b -> [b]

iterate дает нам список b с, и нам нужен список m a с, поэтому я подозреваю b = m a. 

iterate :: (m a -> m a) -> m a -> [m a]

Теперь нам нужен способ преобразовать f :: a -> m a во что-то типа m a -> m a. К счастью, это именно то определение bind: 

(=<<) :: (Monad m) => (a -> m b) -> (m a -> m b)

Итак: 

\f -> iterate (f =<<) :: (a -> m a) -> m a -> [m a]

И чтобы получить наши начальные x :: a в желаемом m a, мы можем использовать return: 

return :: (Monad m) => a -> m a

Итак: 

iterateM f x = iterate (f =<<) (return x)

Pointfreeize по вкусу.

1 голос
/ 03 октября 2011

Ваше рекурсивное использование iterateM заставляет его быть в монаде списка. Вам нужно запустить действие iterateM и вернуть его результат.

Попытка: 

iterateM f x = do
      x' <- f x
      xs <- iterateM f x'
      return $ x':xs
...