Create higher order instance for a list of a type where the instance for type exists

Question

I'm not sure this is possible. I have something like the following class:

data Bar a = Bar1 a | Bar2

class Foo f where
  foo :: f a -> Either [String] a

instance Foo Bar where
  foo (Bar1 x) = Right x
  foo Bar2 = Left ["is Bar2"]

Now I want to be able to define an instance that given an implementation for Foo f implement Foo [f].

So something like this:

data Bar a = Bar1 a | Bar2

class Foo f where
  foo :: f a -> Either [String] a

instance Foo Bar where
  foo (Bar1 x) = Right x
  foo Bar2 = Left ["is Bar2"]

instance Foo f => Foo [f] where
  foo as = foldr reducer (Right []) (foo <$> as)
    where
      reducer (Right n) (Right xs) = Right $ n:xs
      reducer (Left xs) (Right _)  = Left xs
      reducer (Right _) (Left xs)  = Left xs
      reducer (Left xs) (Left ys)  = Left $ xs ++ ys

Where the list instance just accumulates all lefts and if there no lefts it removes the outer list and moves it to the right (can this be written implemented easier?). The instance like this doesn't type check since the type isn't [f] a but [f a]. The type I expect is foo :: [f a] -> Either [String] [a]

I tried to write a type that this does for me:

type ApplyList (f :: Type -> Type) (a :: Type) = [f a]

instance Foo f => Foo (ApplyList f) where
...

But this doesn't work because I guess types do not support currying.

Is there a way to write this correctly?

Any help is appreciated!

Can you add the type of foo you expect for your instance? E.g. something like foo :: Foo f => f [a] -> Either [String] a ? Or what? (Further, I'm pretty sure you don't want [f], which is a rather advanced thing in Haskell due to DataKinds -- and is not a type, e.g. [f] a is ill-kinded.) — chi
@chi That's the problem. [f] a is ill kinded. The type I'm looking for is [f a]. — John Smith
I don't think you can have foo :: [f a] -> Either [String] [a] with your class: your class makes the return type to be Either [String] a which does not depend on f, so that can't be changed in the instances. You'll probably need some changes in your class definition, maybe adding another parameter a to the class, so that it can later be instantiated to [a]. Maybe with some fundep (or type family?). — chi
In the instance you are trying to write you can return a list of a, but the class says you can return only at most one a. So you should rethink what abstraction this type class stands for. One a or many a? Does that depend on f? — Li-yao Xia

John Smith John Smith · Accepted Answer · 2020-05-19T08:08:40

I ended up changing my class to have the fully applied input and output type. It's a little bit clunky but it works.

class Foo f g where
  foo :: f -> Either [String] g

instance Foo (Bar a) a where
  foo (Bar1 x) = Right x
  foo Bar2 = Left ["is Bar2"]

instance Foo f g => Foo [f] [g] where
  foo as = foldr reducer (Right []) (foo <$> as)
    where
      reducer (Right n) (Right xs) = Right $ n:xs
      reducer (Left xs) (Right _)  = Left xs
      reducer (Right _) (Left xs)  = Left xs
      reducer (Left xs) (Left ys)  = Left $ xs ++ ys

Create higher order instance for a list of a type where the instance for type exists

1 Answers