[Haskell-beginners] Return a Foldable instance

[Federico Mastellone]

Thanks James and Antoine, making a new type like ResultType or
FoldableView seems to be an elegant solution!

On Wed, May 4, 2011 at 3:51 PM, James Cook <mokus at deepbondi.net> wrote:
> 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



-- 
Federico Mastellone
Computer Science Engineer - ITBA
".. there are two ways of constructing a software design: One way is
to make it so simple that there are obviously no deficiencies, and the
other way is to make it so complicated that there are no obvious
deficiencies. The first method is far more difficult."

Tony Hoare, 1980 ACM Turing Award Lecture.