I will try again to repair my rushing on the code side I'm interpreting that [0,0,1] -> False [0,1,2,1] -> True To remove the explicit recursion, and noticing the 0 case any (\(x:xs) -> x `elem` xs) . init . tails . filter (/= 0) -- quadratic but exit soon any identity . (zipWith (==) <*> tail) . sort . filter (/= 0) -- n log n , but has to sort always I'm not sure, what the other code should do with the accumulated part , as it accumulates duplicates too and forget about the previous boolean Hope I read it enough carefully now , to be helpful. Best On Wed, 7 Aug 2019 at 13:13, Paolino <paolo.veronelli@gmail.com> wrote:

Pardon, delete my code. I rushed the answer without reading carefully, my bad.

On Wed, 7 Aug 2019 at 13:05, Paolino <paolo.veronelli@gmail.com> wrote:

...

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@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@gmail.com)

*Functional developer @ global.de <http://global.de/>*

--

Paolo Veronelli (paolo.veronelli@gmail.com)

*Functional developer @ global.de <http://global.de/>*

-- Paolo Veronelli (paolo.veronelli@gmail.com) *Functional developer @ global.de <http://global.de/>*

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

There are two important things to say about your e-mail, but one is a lot more important than the other.

And no, I don't want the general code to be specific for lists, thus no extra type signatures or changes to make it more list of Ints.

You did not understand my (and Paolino's) point about using lists. By using lists *internally* you're not making it less generic. The function still works for any foldable. But you are building another foldable *within your function* as a way to check for duplication, that isn't returned. When you build an element, you need to specify it's type (or use a function passed as parameter to build it). In this case, list is just as good as any other foldable for the internal workings. You can use another foldable if you wish, but you need to use some foldable, because Foldable itself is only a behavioural definition that cannot be used directly. Thus, what I personally said about efficiency was in the case that you wanted the user to be able to *specify as an argument* what instance of Foldable to use for this. If you don't care about efficiency, then use lists, or any other foldable of your choice. Let me see if I can make this clearer with an analogy. You go to a workshop and ask them to build a metal bar for you. You say: it needs to be this size, this weight and be able to resist this amount of strength (that would be equivalent to the typeclass, it needs to be Foldable). Now, what would break the transparency that typeclasses and genericity provide would be if they asked you: "what are you going to use this metal bar for?". They don't need to know, as long as they produce a metal bar that fulfills your requirements. So far so good. But now, imagine that you asked them: "I want you to build the metal bar in such a way that it is independent of the tools that you have available". They would be puzzled. Why do you care what tools they use to build the metal bar? You want a metal bar with a set of characteristics, you will get it. How they build the metal bar and how specific that building of the metal bar may be is absolutely irrelevant to you. This is the list. The list (or any other foldable that you wish to use), is just the tool that you use to check for duplicity. It is *not* the output result of your function. So using it does not break genericity in any way. The second, slightly less important point, is about the type signatures. You want GHC to derive the signatures on its own? Fine. Take the code that I provided you, and remove the type signatures. It compiles, it works, and it infers exactly the same type signatures that I provided. There are two reasons for which I think your approach that "it is better if I don't specify the type signatures" is mistaken. First, the reason you want to provide type signatures is because it makes the code clearer. Saying that "GHC should derive the type signatures" is a bit like writing a mono-function program and saying "the compiler should not care about how long my functions are". Type signatures help the programmer understand what the functions do, help you program by making it easier to see if you can use a function or not by looking at its type signature, and make it easier to debug by modularizing the problems. Second, depending on what extensions you use (and you are using RankNTypes and KindSignatures, which are not trivial extensions), type signatures on functions or type annotations might not be avoidable, precisely because of ambiguity. In this particular case, they can be removed, as I said, but there are some programs that are inevitably ambiguous unless you explicitly specify the types. And this is not a GHC limitation, it is a mathematical limitation of the programming model, so type signatures are not optional sometimes. But, as I said, if you really disagree and prefer not to provide type signatures, then don't. The code I provided still works perfectly, and the reason why using lists internally does not break genericity still holds regardless of that. Juan. Quoting Dušan Kolář <kolar@fit.vut.cz> on Wed, 07 Aug 2019 14:38:12 +0200:

Thanks all for the answers, and no, they are not what I was asking for...

Not providing type signatures, yes, no type signatures provided, GHC should derive them on its own. My question was, why it is not able to do that and how force GHC to do that. Without extra type info...

The original type signature was simple: chkDup :: (Eq a, Num a) => [a] -> Bool I would be quite happy to have something similar, just for [] to have some generic type - auto-magically :-)

And no, my intention was not to make it a bit faster for larger inputs, just make clear and clean code without extra type signatures, easy to read and simple to understand. Real-life input has 36 six members at most.

So thank you once again, unfortunately, my conclusion is that writing generic code is not always beneficial - neither for reading nor for generality...

Thank you once again,

Dušan

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

To add and tie this in with the list choice, I must say I said something not entirely correct: Not any foldable that you may want to use is valid. As Jaro showed here, Maybe is a Foldable that would not do what you want. Now, I have no proof of the following, but I'd bet money that I'm not wrong that: List is special as a foldable because it is general. In other words, the function: tolist :: Foldable t => t a -> [a] tolist = foldr (:) [] is such that for any x :: t a where Foldable t, it is true that foldr f v x = foldr f v (tolist x) which is to say, any structure a foldable may have is preserved when transforming into list shape, as a foldable. This is not an argument for saying "let's use lists all the time instead of foldables". Of course not. But, *internally*, you can use lists so that the program can run (because it needs an instance), while knowing that you will not be losing any structure while using lists, so that the overall function will work for any foldable. I think I'll stop my ramblings now, I don't want to overload the list. Quoting Jaro Reinders <jaro.reinders@gmail.com> on Wed, 7 Aug 2019 14:59:43 +0200:

Another issue with not providing a type signature on internal types is that the code can literally change meaning. In this case we can change the meaning of your code by simply adding a type signature:

chkDup ns = fst $ foldr f (False,mempty :: (Semigroup a, Num a, Eq a) => Maybe a) ns where f _ res@(True,_) = res f v res@(_,vs) = if v==0 then (False, vs) else (elem v vs, pure v <> vs)

Now the code doesn't do what you want anymore. How should GHC be able to infer the types if an expression can have two different types that have different meanings?

On 07-08-2019 14:38, Dušan Kolář wrote:

...

Thanks all for the answers, and no, they are not what I was asking for...

Not providing type signatures, yes, no type signatures provided, GHC should derive them on its own. My question was, why it is not able to do that and how force GHC to do that. Without extra type info...

The original type signature was simple: chkDup :: (Eq a, Num a) => [a] -> Bool I would be quite happy to have something similar, just for [] to have some generic type - auto-magically :-)

And no, my intention was not to make it a bit faster for larger inputs, just make clear and clean code without extra type signatures, easy to read and simple to understand. Real-life input has 36 six members at most.

And no, I don't want the general code to be specific for lists, thus no extra type signatures or changes to make it more list of Ints.

So thank you once again, unfortunately, my conclusion is that writing generic code is not always beneficial - neither for reading nor for generality...

Thank you once again,

Dušan

On středa 7. srpna 2019 13:21:27 CEST Juan Casanova wrote:

...

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@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

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

---

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.