[Haskell-beginners] Return a Foldable instance

[James Cook]

On May 4, 2011, at 2:22 PM, Antoine Latter wrote:

> On Wed, May 4, 2011 at 1:08 PM, Federico Mastellone  
> <fmaste at gmail.com> wrote:
>> On Wed, May 4, 2011 at 1:22 PM, Chaddaï Fouché <chaddai.fouche at gmail.com 
>> > wrote:
>>> On Wed, May 4, 2011 at 2:21 PM, Federico Mastellone <fmaste at gmail.com 
>>> > wrote:
>>>> So, is it even possible to write a function with this type:  
>>>> getValues
>>>> :: Foldable f => k -> MultiMap k v -> f v ???
>>>>
>>>
>>> It isn't since there's nothing in the Foldable class that allows you
>>> to build one (only to consume one, do a fold over it, no "unfold").
>>>
>>
>> As it's impossible to build a function like this one below:
>> getValues :: Foldable f => k -> MultiMap k v -> f v
>> I know that it may be too difficult, but wouldn't be great to make
>> this type illegal in Haskell ?
>> You can't make a function that returns a class that has no method  
>> that
>> builds an instance of that class unless another parameter of the
>> function is of that class or allows you to build one instance of that
>> class.
>>
>>> But since this signature is _not_ the one you really want (it says  
>>> you
>>> will deliver any Foldable your caller asks for), this isn't a  
>>> problem,
>>> what you really want is :
>>>
>>>> data ExFoldable a = forall f . (Foldable f) => ExFoldable (f a)
>>
>> This will do the trick and it is better than maintaining an
>> intermediate structure as I previously said.
>> Thank you and Alexander for this tip.
>>
>
> I really think that this is just a more complicated version of making
> your own wrapper type as discussed above.
>
> Both types:
>
>> data ExFoldable a = ...
>
> and
>
>> newtype ResultType a = Result [a]
>> deriving (Foldable)
>
> offer up the exact same API to the caller. The second one is just
> easier to understand and requires fewer advanced language extensions.
>
> And if your goal is optimization, the 'ExFoldable' version is likely
> to be slower for the caller to fold over than if you had converted the
> result to a list and returned it, because with the 'ExFoldable' return
> type the compiler has less information to work with at the call site.
> Keep in mind I haven't benchmarked any of this :-)
>

If you're really dead-set on eliminating lists, I'd suggest that your  
'ResultType' just be a structure that contains a reference to a  
MultiMap and a key, or whatever other information you need to be able  
to implement foldMap.  For example:

 > data FoldableView k v = FoldableView k (MultiMap k v)
 > instance Foldable (FoldableView k) where {- ... -}
 >
 > getValues :: k -> MultiMap k v -> FoldableView k v
 > getValues k m = FoldableView k m

Then your users really can just fold over (a very lightweight view of)  
the MultiMap itself, with no intermediate structures of any kind.

-- James