[Haskell-cafe] Ambiguous types

Wed Aug 7 11:17:27 UTC 2019

To build up on Paolino's answer, and maybe, if you're like me, give  
you a better intuition as to why your code was incorrect, but leading  
to essentially the same answer he gave.

First, you didn't provide us with the type signatures for chkDup and  
f, but I worked with the following ones to start with:

chkDup :: forall a (t :: * -> *) (f :: * -> *). (Eq a, Num a, Foldable  
t, Foldable f, Applicative f, Monoid (f a)) => t a -> Bool

f :: (Num a, Foldable t, Semigroup (t a), Applicative t, Eq a) => a ->  
(Bool, t a) -> (Bool, t a)

This gives me the same error you get even if I define chkDup _ = undefined.

The problem is that you are providing class constraints for the type  
f, which does not appear at all in the signature of the function (t a  
-> Bool), and this makes the typechecker get super confused. Now, I  
know why you thought this was necessary: precisely because of what  
Paolino pointed out: mempty has an undefined type, and you tried to  
fix this by saying "This mempty is of type f, which I don't care for  
the type, just that it is a Semigroup and Applicative". But this is a  
mistake. So, if you just remove the f altogether from the class  
constraints of the chkDup type signature, and leave it like this:

chkDup :: forall a (t :: * -> *) (f :: * -> *). (Eq a, Num a, Foldable  
t) => t a -> Bool

You still get an error, but now you get the actual error message that  
you're looking for: "Could not deduce Foldable t0 arising from a use  
of f".

The right way to fix this is how Paolino said: Specify what Foldable  
you're going to use (recommended: list) (so, use [] instead of  
mempty). The point is, since the type f is not part of the input NOR  
the output of the function chkDup, and instead it is just an internal  
tool that you use to compute chkDup, there's no reason to want to be  
generic about it, there's no advantage in that. The advantage in  
genericity using typeclasses is: 1. If it's in the input, you allow  
the user of the function to provide you with any type that fulfills  
the class. 2. You make it very clear that everything you do with that  
parameter is related to its typeclass instance, as there is no way to  
inspect the actual type. 3. If it's in the output, you don't let users  
of the function make any assumption of what that type might look like,  
other than its typeclass instance.

But in an internal tool that doesn't come from outside and isn't  
output by your function, there's no reason to be generic, just use  
lists. The only reason I could see being argued for wanting to be  
generic would be if you'd like the user to provide you with hints as  
to how to compute the function so that it's more efficient. If you  
really want to go that far, I think there's other ways to do that,  
that I haven't thought of right now.

All in all, the following code works:

chkDup :: forall a (t :: * -> *) (f :: * -> *). (Eq a, Num a, Foldable  
t) => t a -> Bool
chkDup ns = fst $ foldr f (False,[]) ns

f :: (Num a, Foldable t, Semigroup (t a), Applicative t, Eq a) => a ->  
(Bool, t a) -> (Bool, t a)
f _ res@(True,_) = res
f v res@(_,vs) = if v==0 then (False, vs) else (elem v vs, pure v <> vs)

I hope you found that useful.

Juan.

Quoting Paolino <paolo.veronelli at gmail.com> on Wed, 7 Aug 2019 13:05:39 +0200:

> So about the type error, the second element of the tuple has no defined
> type. You can fix it substituting (pure v) with [v] if you want a list
> there.
>
> Also
>
> - chkDup ns = any (`elem` ns)
> - use Set.member to reduce complexity
>
> Best
>
> On Wed, 7 Aug 2019 at 11:53, Dušan Kolář <kolar at fit.vut.cz> wrote:
>
>> Dear Café,
>>
>>
>>
>> I'm trying to solve a couple of examples and exercises just for me. I've
>> come to the point, when I'm trying working code manipulating lists rewrite
>> to work on Foldable (etc.).
>>
>>
>>
>> Nevertheless, I must be doing some mistake, overlooking something, as
>> simple code like this:
>>
>>
>>
>> chkDup [] = False
>>
>> chkDup (0:ns) = chkDup ns
>>
>> chkDup (n:ns) = elem n ns || chkDup ns
>>
>>
>>
>> which works fine, type-checks, can be used within other code, I'm trying
>> to replace with more generic, but probably less efficient and wrong code:
>>
>>
>>
>> chkDup ns = fst $ foldr f (False,mempty) ns
>>
>> where
>>
>> f _ res@(True,_) = res
>>
>> f v res@(_,vs) = if v==0 then (False, vs) else (elem v vs, pure v <> vs)
>>
>>
>>
>> which does not even type-check.
>>
>>
>>
>> Nevertheless, the error message is not too helpful, searching the Internet
>> just confirms it's wrong and that adding AllowAmbiguousTypes would not
>> work. The error message is:
>>
>>
>>
>> helper.hs:49:1: error:
>>
>> • Could not deduce (Foldable f0)
>>
>> from the context: (Eq a, Num a, Foldable t, Foldable f,
>>
>> Applicative f, Monoid (f a))
>>
>> bound by the inferred type for ‘chkDup’:
>>
>> forall a (t :: * -> *) (f :: * -> *).
>>
>> (Eq a, Num a, Foldable t, Foldable f, Applicative f,
>>
>> Monoid (f a)) =>
>>
>> t a -> Bool
>>
>> at helper.hs:(49,1)-(53,80)
>>
>> The type variable ‘f0’ is ambiguous
>>
>> • In the ambiguity check for the inferred type for ‘chkDup’
>>
>> To defer the ambiguity check to use sites, enable AllowAmbiguousTypes
>>
>> When checking the inferred type
>>
>> chkDup :: forall a (t :: * -> *) (f :: * -> *).
>>
>> (Eq a, Num a, Foldable t, Foldable f, Applicative f,
>>
>> Monoid (f a)) =>
>>
>> t a -> Bool
>>
>> |
>>
>> 49 | chkDup ns =
>>
>> | ^^^^^^^^^^^...
>>
>>
>>
>>
>>
>> So is there a nicer and working way, how to change my simple example? Is
>> there a way, how to make it compile? Or is it useless to do that, original
>> function is just fine...
>>
>>
>>
>> Best regards,
>>
>> Dušan
>>
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> To (un)subscribe, modify options or view archives go to:
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>> Only members subscribed via the mailman list are allowed to post.
>
>
>
> --
>
> Paolo Veronelli (paolo.veronelli at gmail.com)
>
>
> *Functional developer @ global.de <http://global.de/>*
>

-- 
The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.