Illegal type synonym family in instance - Haskell

Welcome to the Functional Programming Zulip Chat Archive. You can join the chat here.

Asad Saeeduddin

What's the easiest way to make this work

{-# LANGUAGE TypeFamilies, FunctionalDependencies, LambdaCase #-}
module SOP.Sums where

import MyPrelude

import GHC.Generics

import Data.Void

import Optics

type family Sum (xs :: [*]) :: *
  where
  Sum '[] = Void
  Sum (x ': xs) = Either x (Sum xs)

class Coproduct c xs | c -> xs
  where
  asCoproduct :: Iso' c (Sum xs)

instance Coproduct (U1 p) '[()]
  where
  asCoproduct = iso (\U1 -> Left ()) (either (const U1) absurd)

instance Coproduct (K1 i c p) '[c]
  where
  asCoproduct = iso (\(K1 c) -> Left c) (either K1 absurd)

instance (Functor f, Coproduct (f p) xs) => Coproduct (M1 i c f p) xs
  where
  asCoproduct = iso (\(M1 fp) -> fwd asCoproduct fp) (M1 . bwd asCoproduct)

type family xs ++ ys :: [*]
  where
  '[] ++ xs = xs
  (x ': xs) ++ ys = x ': (xs ++ys)

instance (Coproduct (f p) xs, Coproduct (g p) ys) => Coproduct ((f :+: g) p) (xs ++ ys)
  where
  asCoproduct = iso (\case { L1 fp -> Left fp; R1 gp -> Right $ fwd asCoproduct gp }) (either L1 (R1 . bwd asCoproduct))
Asad Saeeduddin

Right now it gives:

[typecheck] [E] /mnt/data/depot/git/haskell/repos/co-optics/src/SOP/Sums.hs:38:54: error:
    • Illegal type synonym family application in instance: xs ++ ys
    • In the instance declaration for
        ‘Coproduct ((f :+: g) p) (xs ++ ys)’
Lysxia

instance (Coproduct (f p) xs, Coproduct (g p) ys, xs ++ ys ~ zs) => Coproduct ((f :+: g) p) zs perhaps?

Lysxia

You will need more constraints to inject Sum xs and Sum ys into Sum (xs ++ ys).

Asad Saeeduddin

Yeah, I ended up doing the weird hack I resort to in these situations

Asad Saeeduddin
class Append (xs :: [*]) (ys :: [*]) (zs :: [*]) | xs ys -> zs
  where
  appendCoproducts :: Proxy xs -> Proxy ys -> Either (Sum xs) (Sum ys) -> Sum zs

instance Append '[] ys ys
  where
  appendCoproducts _ _ = either absurd id

instance Append xs ys zs => Append (x ': xs) ys (x ': zs)
  where
  appendCoproducts (_ :: Proxy (x ': xs)) (_ :: Proxy ys) = either (either Left (\xs -> Right $ appendCoproducts (Proxy @xs) (Proxy @ys) $ Left xs)) (\ys -> Right $ appendCoproducts (Proxy @xs) (Proxy @ys) (Right ys))

instance (Coproduct (f p) xs, Coproduct (g p) ys, Append xs ys zs) => Coproduct ((f :+: g) p) zs
  where
  asCoproduct = iso _ _
Lysxia

There's usually a compact continuation-passing solution too.

Asad Saeeduddin

Alas, now I've realized I might not have enough information altogether:

class Append (xs :: [*]) (ys :: [*]) (zs :: [*]) | xs ys -> zs
  where
  (|||) :: Proxy xs -> Proxy ys -> Either (Sum xs) (Sum ys) -> Sum zs

instance Append '[] ys ys
  where
  _ ||| _ = either absurd id

instance Append xs ys zs => Append (x ': xs) ys (x ': zs)
  where
  (_ :: Proxy (x ': xs)) ||| (_ :: Proxy ys) = either (either Left (\xs -> Right $ (Proxy @xs ||| Proxy @ys) $ Left xs)) (\ys -> Right $ (Proxy @xs ||| Proxy @ys) (Right ys))

instance (Coproduct (f p) xs, Coproduct (g p) ys, Append xs ys zs) => Coproduct ((f :+: g) p) zs
  where
  asCoproduct = iso
    (\case { L1 fp  -> (Proxy @xs ||| Proxy @ys) $ Left $ fwd asCoproduct fp; R1 gp -> (Proxy @xs ||| Proxy @ys) $ Right $ fwd asCoproduct gp })
    _
Lysxia

What's the error?

Asad Saeeduddin

There's no error, but I've ended up needing to produce Sum zs -> (f :+: g) p

Asad Saeeduddin

idk if I can do that without an extra index or something. maybe I'm not thinking about it clearly though

Asad Saeeduddin

What I need is Iso (Either (Sum xs) (Sum ys)) (Sum zs), right?

Asad Saeeduddin

or can I get away with the unidirectional thing I have now somehow

Lysxia

yes you need Append or whatever constraint you end up with to contain an iso

Lysxia

The continuation-passing way is to use a ternary class, quantifying over "the rest of the sum". Then you won't need an auxiliary Append constraint for the (:+:) instance.

class Coproduct' c rs xs where
  asCoproduct' :: Iso' (Either c (Sum rs)) (Sum xs)
Asad Saeeduddin

@Lysxia You think I can actually implement the cons instance as an iso?

Asad Saeeduddin

without additional type level information I mean

Asad Saeeduddin

I got back up to where I was before, now I need to do the backwards case:

class Append (xs :: [*]) (ys :: [*]) (zs :: [*]) | xs ys -> zs
  where
  (|||) :: Proxy xs -> Proxy ys -> Iso' (Either (Sum xs) (Sum ys)) (Sum zs)

instance Append '[] ys ys
  where
  _ ||| _ = iso (either absurd id) Right

instance Append xs ys zs => Append (x ': xs) ys (x ': zs)
  where
  (_ :: Proxy (x ': xs)) ||| (_ :: Proxy ys) = iso
    (either
      (either Left (Right . fwd (Proxy @xs ||| Proxy @ys) . Left))
      (Right . fwd (Proxy @xs ||| Proxy @ys) . Right))
    _
Lysxia

sure that looks feasible

Asad Saeeduddin

i just filled out the holes, but I don't really get how one direction doesn't destroy some information

Asad Saeeduddin

like, mashing them together

Asad Saeeduddin

ok, so it all works, I'll add a note to do it the right way with the CPS approach later

Asad Saeeduddin

conveniently we can link to messages in this thing, so I won't have to ask you five more times :sweat_smile:

Asad Saeeduddin

Here's the whole thing for anyone who's interested: https://gist.github.com/masaeedu/f80f47bb1fcf8412dccc3edef1bbd21a

Generic coproducts. GitHub Gist: instantly share code, notes, and snippets.