[Haskell-cafe] Ambiguous types

Wed Aug 7 11:21:27 UTC 2019

PS: I didn't even spend much time thinking how I would probably  
implement chkDup differently even for the generic case that you want  
to do. As in, intuition tells me you don't really need an applicative  
monoid internally to do what you're trying to do. But, as I said,  
haven't thought it thoroughly, and with the code I gave you, you get  
what you were trying to do and it's not "wrong". Maybe just overkill.

Quoting Juan Casanova <juan.casanova at ed.ac.uk> on Wed, 07 Aug 2019  
12:17:27 +0100:

> 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.
>
>
> _______________________________________________
> 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.

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