[haskell] Cycle in type synonym declarations

можно ли как-то исправить ситуацию

Нельзя. Синонимы определяемые type раскрываются на стадии компиляции и не создают конструкторов и аккессоров, фактически не влияют на рантайм, поэтому не могут быть рекурсивными (иначе как раскрыть такой синоним?).

получилось только так

Лучше так:

newtype State = State { runState :: (Char, Int) -> (Failable Action, State) }

Только если это state transformer, то правильно так:

newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }

type State s = StateT s Identity

можно сразу из mtl его брать.

newtype и runState плюсую, а на state transformer не похоже совершенно.

По-моему, это стрелка:

{-# LANGUAGE Arrows, TupleSections #-}
module StateArr where
import Prelude hiding (id, (.))
import Control.Arrow
import Control.Category
newtype StateArr input output = StateArr {runStateArr :: input -> (output, StateArr input output)}
instance Category StateArr where
    id = arr id
    sa2 . sa1 = StateArr {runStateArr = \input -> let ~(middle, sa1') = runStateArr sa1 input in second (. sa1') (runStateArr sa2 middle)}
instance Arrow StateArr where
    arr h = arrh where arrh = StateArr {runStateArr = (, arrh) . h}
    first sa = StateArr {runStateArr = \(~(input, z)) -> ((, z) *** first ) (runStateArr sa input)}

Я бы даже сказал

instance ArrowChoice StateArr where
    left sa = StateArr {runStateArr = second left . (first Left . runStateArr sa ||| (, sa) . Right)}
twist ~(~(a, b), c) = ((a, c), b)
instance ArrowLoop StateArr where
    loop sa = StateArr {runStateArr = second loop . loop (twist . runStateArr sa)}

а на state transformer не похоже совершенно

Вот и я подумал - где такая штука может понадобится, потому что это, вроде как,

type State = Mu (MTL.State (Either (Char, Int) (Failable Action)))

По-моему, это стрелка

Type level fixed point от state transformer-а! ;)

type State = Mu (MTL.State (Either (Char, Int) (Failable Action)))

Чего-то как-то не того. У ТС тип по (Char, Int) контравариантен, а по Failable Action ковариантен. Как они вдруг оказались в одинаковых положениях?

Как они вдруг оказались в одинаковых положениях?

Иначе, без суммы типов, вариант TC в MTL.State никак не влезет (так как там тип входа и тип основного выхода должны совпадать). Так что то определение покрывает собой четыре разных варианта - контравариантные/ковариантные по (Char, Int)/Failable Action.

Чтобы точно зафиксировать вариантность нужно иметь ST с трёмя разными типами (входа, основного и побочного выхода; плюс монадический тип (* -> *), конечно) это нужно новую библиотеку трансформеров писать. И по-честному там должны быть бифункторные классы типов а не Arrows.

Так что то определение покрывает собой четыре разных варианта

Т.е., нифига это не то же самое. В топку.

У ТС там - в чистом виде Automaton (->) (Char, Int) (Failable Action). См. пакет arrows, модуль Control.Arrow.Transformer.Automaton.

См. пакет arrows

Посмотрю.

А как с помощью Arrow(Choice?) задать бифунктор для произвольного типа Foo :: * -> * -> * ?

А как с помощью Arrow(Choice?) задать бифунктор для произвольного типа Foo :: * -> * -> * ?

Чего-чего?

Вообще-то, если тип не является бифунктором, то хоть с Arrow, хоть без Arrow, но задавать там нечего.

Чего-чего?

Функтор у нас отображает типы в type level и термы во время вычисления, а бифунктор делает это с парами типов:

class BiFunctor f where
  bimap :: (a -> a') -> (b -> b') -> f a b -> f a' b'

например:

instance BiFunctor (,) where
  bimap f g (x, y) = (f x, g y)

для (,) равно как и для любого другого типа с kind-ом (* -> * -> *), например, с ST:

newtype StateT m i r o = StateT { runStateT :: i -> m (r, o) }

type State i = StateT Identity i

instance (Functor m) => BiFunctor (StateT m i) where
  bimap f g x = StateT $
    \i -> fmap (\ ~(r, o) -> (f r, g o)) $
      runStateT x i

А у Arrow, ЕМНИП, там так не получится, они предназначены для того чтобы моделировать стрелки - когда для типа который играет роль стрелки определены Category, Arrow и ArrowChoice мы таки получаем бифунктор в контексте этих стрелок, но работает он только для одного типа (,) (так как (,) и Either зашиты в определения Arrow).

Есть какие-то причины по которым нельзя использовать 2- версии функторов и монад, а нужно использовать Arrow? (если что, 2- версию монады я с ходу не определю).

Чисто ради интереса:

class BiFunctor f where
  bimap :: (a -> a') -> (b -> b') -> f a b -> f a' b'

newtype StateT m i o r = StateT { runStateT :: i -> m (o, r) }

type State = StateT Identity

instance (Functor m) => BiFunctor (StateT m i) where
  bimap f g x = StateT $
    \i -> fmap (\ ~(r, o) -> (f r, g o)) $
      runStateT x i

newtype Mu f = In (f (Mu f))

type StateR = Mu (State (Char, Int) (Failable Action))

Но Control.Arrow.Transformer.Automaton, видимо, кошернее.

Поток сознания какой-то. Ни черта не понимаю.

Бифунктор в твоём понимании ковариантен по первому аргументу. Стрелка - контравариантна. Следовательно, стрелка - не бифунктор.

При чём тут (,) и Either я не врубаюсь. Как это относится к предыдущему вопросу - тоже.

type StateR = Mu (State (Char, Int) (Failable Action))

Ещё раз: это не имеет НИКАКОГО отношения к исходному посту.

Поток сознания какой-то. Ни черта не понимаю.

Тогда ладно.

Следовательно, стрелка - не бифунктор

Так а на самом деле как? Бифунктор или нет?

это не имеет НИКАКОГО отношения к исходному посту.

Как и стрелки.

Так а на самом деле как? Бифунктор или нет?

Я уже сказал: НЕТ. На самом деле нет. Воистину нет. Мамой клянусь, нет.

Как и стрелки.

Стрелки имеют опосредованное отношение: приведённый ТС тип (после исправления) можно сделать стрелкой. Что, возможно, позволит работать с ним несколько более удобным образом.

Я уже сказал: НЕТ.

В «Categorical semantic for arrows» доказывается что, в некоторой степени, ДА (lemma 4.1.).

kyz, реквестирую рассказ про ситуацию в которой возникла необходимость в таком типе.

В «Categorical semantic for arrows»

Там как раз и говорится о контравариантности по первому аргументу. То есть, если бы ты определил бифунктор как

class Bifunctor f where
    bimap :: (a' -> a) -> (b -> b') -> f a b -> f a' b'

Там как раз и говорится о контравариантности по первому аргументу.

Это дифунктор. В category-extras обычный бифунктор написан с обычной сигнатурой (иначе как инстансы-то писать?), а дуальный - как в той статье.

Это дифунктор.

Ну как кофунктор, он тоже контравариантный, а обычный функтор - ковариантный.

>kyz, реквестирую рассказ про ситуацию в которой возникла необходимость в таком типе.

конечный автомат