Есть ли в общем случае складной функтор, эквивалентный голове / хвосту? - PullRequest
Новая
       58

Есть ли в общем случае складной функтор, эквивалентный голове / хвосту?

0 голосов
/ 10 июня 2018

Я хотел бы выразить следующий код на Haskell, используя только алгебру функторов (т.е. - , а не , полагаясь на какой-либо конкретный тип контейнера, например List): 

ys = zipWith (+) (head xs : repeat 0)
                 (tail xs ++ [y])

Мне кажется, что должен быть способ сделать это, полагаясь только на Foldable (или, может быть, Traversable), но я этого не вижу.

Мне интересно:

  1. Существует ли общее понятие first и rest для складных / перемещаемых функторов?
  2. Есть лили принятый идиоматический способ, использующий только алгебру функторов, для перемещения содержимого функтора Foldable / Traversable?(Обратите внимание, что приведенные выше вычисления могут быть описаны на английском языке как «Сдвиг на одно значение справа и добавьте обратно значение, которое падает слева, к новому первому значению.»)

Ответы [ 4 ]

0 голосов
/ 12 июня 2018

Для поворота вам не нужны какие-то уродливые частичные функции.Этот странный Applicative сделает свое дело. 

data Foo a t where
  Cons :: (a -> q -> t) -> a -> Foo a q -> Foo a t
  Nil :: t -> Foo a t

instance Functor (Foo a) where
  fmap f (Cons g x xs) = Cons (\p q -> f (g p q)) x xs
  fmap f (Nil q) = Nil (f q)

instance Applicative (Foo a) where
  pure = Nil
  liftA2 f (Nil t) ys = f t <$> ys
  liftA2 f (Cons g x xs) ys = Cons (\a (q,b) -> f (g a q) b) x (liftA2 (,) xs ys)

Вы можете повернуть Foo: 

rot :: Foo a t -> Foo a t
rot n@(Nil _) = n
rot (Cons g0 a0 as0) = go g0 a0 as0
  where
    go :: (a -> q -> t) -> a -> Foo a q -> Foo a t
    go g a n@(Nil _) = Cons g a n
    go g a (Cons h y ys) = Cons g y (go h a ys)

и запустить один, чтобы получить результат: 

runFoo :: Foo a t -> t
runFoo (Nil t) = t
runFoo (Cons g x xs) = g x (runFoo xs)

Собрав все вместе, 

rotate :: Traversable t => t a -> t a
rotate = runFoo . rot . traverse (\a -> Cons const a (Nil ()))

Тогда rotate [1..10] = [2..10] ++ [1].

0 голосов
/ 10 июня 2018

Первая часть вашего вопроса (сочетающая первое значение структуры с одной вещью и оставляющая все то же самое) может быть выполнена простым способом с Traversable.Мы будем использовать State, начнем с функции, которую мы хотим применить, и сразу изменим ее на id. 

onlyOnHead :: Traversable t => (a -> a) -> t a -> t a
onlyOnHead f xs = evalState (traverse go xs) f where
    go x = do
        fCurrent <- get
        put id
        return (fCurrent x)

Вы можете вращать элементы с похожей идеей: мы будем вращатьсписок и прочее, что в нашем State как элемент для рисования элементов. 

rotate :: Traversable t => t a -> t a
rotate xs = evalState (traverse go xs) (rotateList (toList xs)) where
    rotateList [] = []
    rotateList vs = tail vs ++ [head vs]

    go _ = do
        v:vs <- get
        put vs
        return v
0 голосов
/ 11 июня 2018

Спасибо всем, кто откликнулся!

Обратите внимание, что Библиотека типовых типов Конала Эллиота также имеет некоторые полезные механизмы в этом отношении.

0 голосов
/ 10 июня 2018

Вы можете найти первый или последний элемент Foldable, используя моноиды First или Last из Data.Monoid. 

foldMap (Last . Just)  :: Foldable t => t a -> Last a
foldMap (First . Just) :: Foldable t => t a -> First a

Все Foldable конвертируются в список,и так как вы можете найти начало и конец списка, вы можете сделать это для любого Foldable. 

toList = foldr (:) [] :: Foldable t => t a -> [a]

Тем не менее, хвост будет иметь тип списка, а не тип Foldable (если это не было слишком списком).В конечном итоге это происходит потому, что не все, что является Foldable, могут реализовывать несвязанные объекты.Например:

data Pair a = Pair a a

Это Foldable, но вы не можете представить хвост Pair, используя Pair.

...