How can I return a non-concrete value from a function that supports some API?

Question

I'm building an API between two models. I don't care if it returns a [] or Seq or anything Foldable is fine. But if I try to do that, I get errors. ``` module Main where import Prelude hiding (foldr) import Data.Foldable import Data.Sequence data Struct = Struct main = do print $ foldr (+) 0 $ list Struct print $ foldr (+) 0 $ listFree Struct listFree :: Foldable f => a -> f Int listFree s = singleton 10 class TestClass a where list :: Foldable f => a -> f Int instance TestClass Struct where list s = singleton 10 ``` Both the listFree and the list definitions give the same error: ``` TestFoldable.hs:19:12: Could not deduce (f ~ []) from the context (Foldable f) bound by the type signature for list :: Foldable f => Struct -> f Int at TestFoldable.hs:19:3-15 `f' is a rigid type variable bound by the type signature for list :: Foldable f => Struct -> f Int at TestFoldable.hs:19:3 In the expression: [10] In an equation for `list': list s = [10] In the instance declaration for `TestClass S…

Accepted Answer

sepp2k already provided a good answer, but allow me to take a similar but slightly different angle. What you have done is provide result-type polymorphism. You wrote:

```
listFree :: Foldable f => a -> f Int
```

What this does is promise that you can produce any foldable that the user may need. You, of course, could never keep this promise because `Foldable` doesn't provide any constructor-like functions.

So what you're trying to do deals with generics. You want to make a weak promise: the function `listFree` will produce some `Foldable`, but in the future, it may change. You might implement it with a regular list today, but later, you might re-implement it with something else. And you want this implementation detail to be just that: an implementation detail. You want the contract for that function (the type signature) to remain the same.

Sounds like a job for yet another weird and confusing Haskell extension! Existential Quantification!

```
{-# LANGUAGE ExistentialQuantification #-}

import Prelude hiding (foldr, foldl, foldr1, foldl1)
import Data.Foldable

data SomeFoldable a = forall f. Foldable f => F (f a)

foo :: SomeFoldable Int
foo = F [1,2,3]
```

Here I've provide a value `foo`, but it has the type `SomeFoldable Int`. I'm not telling you which `Foldable` it is, simply that it is some foldable. `SomeFoldable` can easily be made an instance of `Foldable`, for convenience.

```
instance Foldable SomeFoldable where
  fold (F xs) = fold xs
  foldMap f (F xs) = foldMap f xs
  foldr step z (F xs) = foldr step z xs
  foldl step z (F xs) = foldl step z xs
  foldr1 step (F xs) = foldr1 step xs
  foldl1 step (F xs) = foldl1 step xs
```

Now we can do `Foldable` things with `foo`, for example:

```
> Data.Foldable.sum foo
6
```

But we can't do anything with it besides what `Foldable` exposes:

```
> print foo
No instance for (Show (SomeFoldable Int)) blah blah blah
```

It's easy to adapt your code to work as desired:

```
data Struct = Struct

main = do
  print $ foldr (+) 0 $ list Struct
  print $ foldr (+) 0 $ listFree Struct

listFree :: a -> SomeFoldable Int
listFree s = F [10]

class TestClass a where
  list :: a -> SomeFoldable Int

instance TestClass Struct where
  list s = F [10]
```

But remember, Existential Quantification has its drawbacks. There is no way to unwrap `SomeFoldable` to get the concrete `Foldable` underneath. The reason for this is the same reason that your function signature was wrong at the beginning: it promises result-type polymorphism: a promise it cannot keep.

```
unwrap :: Foldable f => SomeFoldable a -> f a   -- impossible!
unwrap (F xs) = xs    -- Nope. Keep dreaming. This won't work.
```

How can I return a non-concrete value from a function that supports some API?

Solution

Problem