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

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

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

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

Я задаюсь вопросом:

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

haskell shift functor traversable foldable
person dbanas    schedule 10.06.2018    source источник
comment
Не используя класс Foldable, но гораздо более удобный и общий: _head и _tail из библиотеки линз.   -  person leftaroundabout    schedule 11.06.2018

Ответы (4)


arrow_upward
4
arrow_downward

Первая часть вашего вопроса (объединение первого значения структуры с одной вещью и оставление остальных неизменными) может быть выполнена простым способом с помощью 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
person Daniel Wagner    schedule 10.06.2018
comment
Другой способ с Traversable — rotate xs = ys where (x0, ys) = mapAccumR (\x y -> (y, x)) x0 xs. (Или аналогичный трюк с runState, наверное.) - person David Fletcher; 10.06.2018
comment
@DavidFletcher Очень круто! - person Daniel Wagner; 10.06.2018
comment
Интересный. Это также показывает, что если тип T a должен быть непрозрачным и удовлетворять некоторому инварианту (скажем, красно-черному дереву), то он может быть превращен в Foldable, но не должен быть Traversable. - person chi; 11.06.2018
comment
@чи Почему? Инвариант красно-черных деревьев находится на корешке, а не в содержании, и traverse точно сохраняет корень. Так что нет проблем. - person Daniel Wagner; 11.06.2018
comment
@DanielWagner То, что я написал, вводит в заблуждение, извините. Я думал об инварианте BST (который является лишь частью красно-черного инварианта). Это было бы нарушено вращением. (Мы не можем разрешить Functor и здесь, так как это уже позволило бы нарушить инвариант BST) - person chi; 11.06.2018
comment
@chi О, конечно. Но также подумайте о Set и Map — у каждого есть инвариант, и, следовательно, Set не может поддерживать Functor или любой другой забавный класс, но Map может поддерживать Functor и Traversable, потому что инвариант находится на его ключах, которых нет у этих экземпляров. т трогать. - person Daniel Wagner; 11.06.2018

arrow_upward
6
arrow_downward

Вы можете найти первый или последний элемент 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, может реализовать uncons. Например:

data Pair a = Pair a a

Это Foldable, но вы не можете представить хвост Pair с помощью Pair.

person erisco    schedule 10.06.2018
comment
Хотя получение головы и хвоста может не иметь смысла, оставаясь в заданном типе Foldable, вращение любого Foldable при сохранении точно такого же позвоночника кажется четко определенной операцией. Просто не тот, который доступен, я не думаю. например для Pair, rotate (Pair x y) = Pair y x - совершенно крутая операция. - person Daniel Wagner; 10.06.2018
comment
@DanielWagner интересно. Ну, возможно, в схемах рекурсии есть что-то, что может помочь. foldr не будет резать. - person erisco; 10.06.2018
comment
@DanielWagner Думаю, тебе понадобится Traversable - person Benjamin Hodgson♦; 10.06.2018
comment
@BenjaminHodgson Спасибо, ваш комментарий, хотя это должно было быть очевидным в ретроспективе, рассказал мне, как реализовать то, о чем меня просили. Я обновил свой ответ с учетом вашего понимания. знак равно - person Daniel Wagner; 10.06.2018

arrow_upward
1
arrow_downward

Чтобы вращаться, вам не нужны никакие уродливые частичные функции. Этот странный 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].

person dfeuer    schedule 11.06.2018

arrow_upward
0
arrow_downward

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

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

person dbanas    schedule 11.06.2018