Использование класса типов для шаблона аргумента variadi c в Haskell

Question

Скажем, у меня есть соглашение в Haskell, где я определяю ряд функций, таких как:

data Node = MkNode

s0 :: Node -> s -> Node
s0 a _ = a

s1 :: (s -> a) -> (a -> Node) -> s -> Node
s1 a b c = b (a c)

s2 :: (s -> a) -> (s -> b) -> (a -> b -> Node) -> s -> Node
s2 a b c d = c (a d) (b d)

s3 :: (s -> a) -> (s -> b) -> (s -> c) -> (a -> b -> c -> Node) -> s -> Node
s3 a b c d e = d (a e) (b e) (c e)

Если возможно, я хотел бы определить функцию sn, которая принимает переменное число аргументов, всегда с этим шаблоном. Я видел подобные вещи до использования классов типов, но я не могу понять, как это сделать в этом случае. Например, я могу представить:

class NAble elt where
    sn :: elt -> state -> Node

instance NAble Node where
    sn elt _ = elt

Но тогда я застрял. Я не уверен, каким будет рекурсивное определение. Возможно, что-то вроде:

instance (NAble b) => NAble (a -> b) where
    sn eltMaker state = ss (eltMaker state) state

Но это, очевидно, не совсем верно. Не уверен, что это возможно, но было бы здорово, если бы это было так. Конечно, порядок аргументов может измениться, если это поможет сделать это правильно, но было бы очень хорошо, чтобы это сработало. Любая помощь будет оценена!

Answer 1

Если вы разместите аргументы в несколько ином порядке - с первым аргументом s, а с функцией, создающей Node - вторым - это станет намного проще. Тогда семейство типов исправит вас:

{-# LANGUAGE TypeFamilies #-}

data Node = MkNode

class NAble t where
    type Ret t s
    sn :: s -> t -> Ret t s

instance NAble Node where
    type Ret Node s = Node
    sn s mkNode = mkNode

instance NAble t => NAble (a -> t) where
    type Ret (a -> t) s = (s -> a) -> Ret t s
    sn s mkNode fa = sn s (mkNode (fa s))

Но позвольте мне также порекомендовать альтернативу. Посмотрите на шаблон, который использует стандартная библиотека:

pure   :: Applicative f => (               t)                      -> f t
fmap   :: Applicative f => (a ->           t) -> f a               -> f t
liftA2 :: Applicative f => (a -> b ->      t) -> f a -> f b        -> f t
liftA3 :: Applicative f => (a -> b -> c -> t) -> f a -> f b -> f c -> f t

Взяв f~(->) s и t~Node, мы получим:

pure   :: (               Node)                                     -> s -> Node
fmap   :: (a ->           Node) -> (s -> a)                         -> s -> Node
liftA2 :: (a -> b ->      Node) -> (s -> a) -> (s -> b)             -> s -> Node
liftA3 :: (a -> b -> c -> Node) -> (s -> a) -> (s -> b) -> (s -> c) -> s -> Node

Что если людям, использующим стандартную библиотеку, нужно liftA4 или выше? Обычно они затем переключаются на цепочку (<*>) использования вместо:

(<*>) :: (s -> a -> Node) -> (s -> a) -> s -> Node
(f <*> g) s = f s (g s)

{-# MAKE_THE_PROGRAMMER_INLINE liftAn #-}
liftAn mkNode f1 f2 ... fn = pure mkNode
    <*> f1
    <*> f2
    ...
    <*> fn