How do I conditionally declare an instance?

Question

How do I say an instance of B could be made for those m s that are instances of A but say nothing about other m s:

-- A.hs
module A where 
class A m -- m :: * -> *

-- B.hs, totally unrelated to A
module B where

class B m

-- Utilities.hs
module Utilities where

given A m then instance B m -- like given in Scala 3

Please note I do not want to say :

class A => class B -- B requires A

The B does not and should not know about A. At the class level B has nothing to do with A. B is defined solely in terms of its Minimal Complete Definition which is expressed after its where clause (not show here) and has no knowledge of A or any other class. In fact B is standalone.

I also do not want to say :

instance A m => B m -- *all* m are B, this requires A m as well


-- actually this errors out with a "constraint is no smaller than head" 
-- which is fixed by `newtype`ing around the `m` in `B`
-- but this is besides the point

This says all ms are Bs and also requires that all m also be As which is not true and not what I want to say. This is not what the Scala line (blow) is saying.

What I want to say is exactly this: There is a B, it defines a certain interface. There is also an totally unrelated A. B is not defined in terms of A nor does it require A in any way at its definition site. Now someone else comes along and knows a way to make an instance of B for an m if there is an instance of A for it.

In Scala I could easily say:

implicit def fromA[M: A]: B[M] = ...

This is saying if you can prove that M is an A (in Scala this is achieved by bringing an implicit A[M] into scope) then I can automatically construct B instances for M. In particular this does not force B on all Ms and is not an error if A[M] does not hold for some M. You are at liberty to construct B for an M all by yourself. The (second) Haskell code above is not equivalent to this Scala code.

I'm looking for an equivalent in Haskell

UPDATE Apparently there is no way to do this in Haskell

UPDATE 2 This is the concrete case behind this question Can't code my component in a tagless-final way / using type classes and instances

"This says all m are B and they also must be A", no, it means that all `m`s for which ` m` holds, are instances of `B`. — Willem Van Onsem, Mar 04 '23 at 21:47
@WillemVanOnsem It kinda does say "all `m` are `B`, but you can't use that without proving `A m`". The instance would match anything (any other instance would overlap), just imposing an additional constraint. — Ben, Mar 04 '23 at 21:53
@WillemVanOnsem that's what I thought at first but in actuality it says : all `m` are `B` and there is more ! they must be also `A`s . So if `A m` is not proven it is in fact an error, not a condition to opt in (or not) on `B` depending on wether `m` does in fact have an `A` instance or not — Ashkan Kh. Nazary, Mar 04 '23 at 22:41
I think you're misguided in wanting to do that, but +1 because it is definitely common to think that it should be possible, even sensible – but it's not. There _are_ various ways to achieve something similar to what you envision, but they're all a bit arcane. It would help if you gave a bit more context for _why_ you actually want it. — leftaroundabout, Mar 04 '23 at 23:07
(And regarding `instance A m => B m`: you're right in your interpretation, but Willem Van Onsem is _also_ right – it depends on whether one thinks in classical logic or intuitionistic.) — leftaroundabout, Mar 04 '23 at 23:09
@leftaroundabout kindly see https://stackoverflow.com/q/75642815/369489 — Ashkan Kh. Nazary, Mar 05 '23 at 14:10

Daniel Wagner · Answer 1 · 2023-03-05T02:34:39.053

What you want can't be done^*; all the things that already have an A instance will have to explicitly be listed as B instances, too. But you can minimize the boilerplate.

If you control the definition of B, you can use DefaultSignatures:

class A m where foo :: m -> m -> m

instance A Int  where foo = {- ... -}
instance A Bool where foo = {- ... -}
instance A Char where foo = {- ... -}

class B m where
    bar :: m -> m -> m -> m
    default bar :: A m => m -> m -> m -> m
    bar m0 m1 m2 = foo (foo m0 m1) m2

-- N.B. no instance body needed
instance B Int
instance B Bool
instance B Char

If you don't control the definition of B, you can make a wrapper newtype and use DerivingVia, possibly tossing in StandaloneDeriving if you also don't control the definitions of the types that are already instances of A.

class A m where foo :: m -> m -> m

instance A Int  where foo = {- ... -}
instance A Bool where foo = {- ... -}
instance A Char where foo = {- ... -}

class B m where
    bar :: m -> m -> m -> m

newtype BViaA m = BViaA m

instance A m => B (BViaA m) where
    bar (BViaA m0) (BViaA m1) (BViaA m2) = BViaA (foo (foo m0 m1) m2)

-- still no body 
deriving instance B Int  via (BViaA Int )
deriving instance B Bool via (BViaA Bool)
deriving instance B Char via (BViaA Char)

See also:

^* Okay. What you want can't be sanely done. I believe there are contortions you can play with IncoherentInstances, but they're fragile and I strongly recommend against them.

score 1 · Answer 2 · answered Mar 04 '23 at 21:50

1

instance A m => B m

No, this is what you want. This says "Whenever something is an instance of A, make it an instance of B using these rules. You may also need FlexibleContexts to get around the constraint problem. FlexibleContexts is one of many Haskell extensions that's ultimately harmless and used in many projects every day.

class A m => B m

This is what you're thinking of. It says "In order for something to be an instance of B, it must already be an instance of A. You declare that constraint when you declare the class the first time. When you put a constraint on an instance, it quantifies the instance.

answered Mar 04 '23 at 21:50

Silvio Mayolo

62,821
6
74
116

No and No :D the first line you posted doesn't compile and needs a `newtype` around the `m` in `B` but even then this is not what I want to say. The second line says "B requires A" (at the class level, not instance level) which is not what I want to say. `B` is not related nor requires `A` in definition (class level). I want to say *one* way of getting an instance of `B m` is to give an `A m` – Ashkan Kh. Nazary Mar 04 '23 at 22:22
"One way of getting an instance" And that's the problem. That's called the newtype pattern. Haskell doesn't play the game of having a bunch of candidate instances for the same type. Haskell takes the view that, for any given type, there is at most one canonical, perfect, ideal, Platonic instance of the class for that type. If we can find it, great! If we can't find it, then either it doesn't exist or it's simply defined somewhere else that we're not yet aware of (the latter case should not occur if you follow good orphan rules). – Silvio Mayolo Mar 04 '23 at 22:25
1

@AshkanKh.Nazary Haskell doesn't use constraints on an instance to choose between instances, because that would require it to commit to there *not* being an instance whenever it wants to choose a different one (and such an instance might actually be used in this program, just not imported into this module). You simply can't follow every design pattern you would use in a different language in Haskell. There *is* `OverlappingInstances` that can be used to get closer to what you want, but I really don't recommend it if you're not very familiar with how the "normal" instance system works first. – Ben Mar 04 '23 at 22:34
@SilvioMayolo edited to make my intent more clear. I didn't know the `newtype` solution is actually a legitimate pattern rather than a work around to make the compiler happy. Still it feels not-the-haskell-way to me. I mean, why the need for it if this was intended ? – Ashkan Kh. Nazary Mar 04 '23 at 22:38
2

@AshkanKh.Nazary In the Scala design, you can have situations where adding an instance somewhere can *change* the meaning of code that was already compiling before. The Haskell design tries to avoid this (the only "hole" is that orphan instances are a warning and not an error). Haskell instances and classes *determine behavior globally as a function of type*, in such a way if that a given piece of code compiles, then no new instances could change its meaning. As a consequence, If there are multiple "ways" to assign a behavior to a type, you need to use `newtype`s to specify what you want. – HTNW Mar 04 '23 at 23:16
1

@AshkanKh.Nazary And this isn't just a missing feature of the compiler, it's a language design decision that is deeply embedded into the ecosystem. For example `Data.Map` uses `Ord` instances to lookup keys; a given `Map` assumes that no matter who it is passed to, the `Ord` instance used will always be the same because there's only one `Ord` instance for the key type. Relaxing that assumption means you have to totally redesign `Map`; now it needs to store the `Ord` instance rather than relying on it being passed (which massively complicates any operation that works on *two* `Map`s, etc). – Ben Mar 05 '23 at 04:08

Dmytro Mitin · Answer 3 · 2023-03-05T17:33:54.997

0

In Scala I could easily say:
implicit def fromA[M: A]: B[M] = ...
I'm looking for an equivalent in Haskell

Scala implicit def fromA[M: A]: B[M] = ... says that if a data type M is an instance of the type class A then it's an instance of the type class B.

The literal translation of

// Scala

trait A[F[_]]
trait B[F[_]]

implicit def fromA[M[_]: A]: B[M] = new B[M] {}

trait C[X]
implicit val ac: A[C] = new A[C] {}

trait D[X]
implicit val bd: B[D] = new B[D] {}

trait E[X]

implicitly[A[C]]
implicitly[B[C]]
//implicitly[A[D]] // doesn't compile
implicitly[B[D]]
//implicitly[A[E]] // doesn't compile
//implicitly[B[E]] // doesn't compile

https://scastie.scala-lang.org/DmytroMitin/Nz1BZQwEQfu6HFQpzBKNww/7

is

-- Haskell

{-# LANGUAGE UndecidableInstances, AllowAmbiguousTypes #-}

import Data.Kind (Type)
     
class A (m :: Type -> Type)
     
class B (m :: Type -> Type)
     
instance A m => B m
     
data C (a :: Type)
     
instance A C
     
data D (a :: Type)
     
instance {-# OVERLAPPING #-} B D
     
data E (a :: Type)
     
implicitly :: a => ()
implicitly = ()
     
test = implicitly @(A C)
test1 = implicitly @(B C)
--test2 = implicitly @(A D) -- doesn't compile
test3 = implicitly @(B D)
--test4 = implicitly @(A E) -- doesn't compile
--test5 = implicitly @(B E) -- doesn't compile

https://ideone.com/iZtAyh

Here I defined three data types C, D, E. C is an instance of A (and therefore automatically of B), D is an instance of B but not of A, E isn't an instance of any of them.

So either you want instance A m => B m in Haskell or you wanted not implicit def fromA[M[_]: A]: B[M] = ??? in Scala.

On the other hand, this

// Scala

trait A[F[_]]
trait A1[F[_]]
trait B[F[_]]

implicit def fromA[M[_]: A]: B[M] = new B[M] {}
implicit def fromA1[M[_]: A1]: B[M] = new B[M] {}

trait C[X]
implicit val ca: A[C] = new A[C] {}
trait D[X]
implicit val da1: A1[D] = new A1[D] {}

implicitly[B[C]] // compiles
implicitly[B[D]] // compiles

https://scastie.scala-lang.org/DmytroMitin/SpuuQYfqQZibQk6EiVQnHw

is not possible in Haskell

-- Haskell

{-# LANGUAGE UndecidableInstances #-}

class A (m :: * -> *)

class A1 (m :: * -> *)

class B (m :: * -> *)

instance A m => B m

instance {-# OVERLAPPING #-} A1 m => B m

data C a

instance A C

data D a

instance A1 D

implicitly :: a => ()
implicitly = ()

test = implicitly @(B C)
test1 = implicitly @(B D)

https://ideone.com/mXXug0

error:
  Duplicate instance declarations:
    instance A m => B m
    instance [overlapping] A1 m => B m

This is not fixable with OVERLAPPING/OVERLAPPABLE.

How to implement `Constraint` reflection? [Ad-Hoc polymorphism based on available Constraints]

Take action based on a type parameter's typeclass?

edited Mar 05 '23 at 17:33

answered Mar 04 '23 at 23:45

Dmytro Mitin

48,194
3
28
66

Haskell `instance A m => B m` does *not* have the same meaning as Scala `implicit def fromA[M[_]: A]: B[M] = ???`. In fact that is the reason I arrived at the question. As the other answer states, this is simply not possible to express in Haskell. – Ashkan Kh. Nazary Mar 05 '23 at 08:39
@AshkanKh.Nazary *"does not have the same meaning as Scala"* Could you be more specific? What exactly do you mean to be possible with `implicit def fromA[M[_]: A]: B[M] = ???` and not possible with `instance A m => B m`? *"In fact that is the reason I arrived at the question"* Well, that's what you wrote in your question, that you're looking for the equivalent. Maybe you could edit your question to make it clearer. I'm afraid now it's quite confusing. – Dmytro Mitin Mar 05 '23 at 11:52
(for some reason I can't tag you) The Scala code says "*one* way of getting a B[M] is as follows, only that A[M] should hold". Your Haskell code says "*all* m are B and they should also be A". It is *not* an error if the Scala code can't find an `A[M]` for some `M`, it just means they can't get a `B[M]` from this particular function. The Haskell code raises an error if `A[M]` is not satisfied in usage site. The question rightly sates its purpose, you got confused because you hold a wrong assumption that your Haskell code does what the Scala line is doing. It does not. – Ashkan Kh. Nazary Mar 05 '23 at 12:48
I updated the question to better explain the difference – Ashkan Kh. Nazary Mar 05 '23 at 13:02
@AshkanKh.Nazary Thanks for your reply. I'm afraid verbal formulations are confusing. Do you have code sample showing the difference that is important for you? I'm trying to figure out what you're after. Scala says that if a data type `M` is an instance of the type class `A` then it's an instance of the type class `B`. You repeated several times that Haskell says that all `m` are `B`. I'm not sure I completely understand what you mean. Here is Scala code https://scastie.scala-lang.org/DmytroMitin/Nz1BZQwEQfu6HFQpzBKNww/7 and Haskell https://ideone.com/iZtAyh – Dmytro Mitin Mar 05 '23 at 13:58
@AshkanKh.Nazary I defined three data types `C`, `D`, `E`. `C` is an instance of `A` (and therefore automatically of `B`), `D` is an instance of `B` but not of `A`, `E` isn't an instance of any of them. So what is the difference exactly that is important for you? Scala manages instances via candidates, specificity, priorities, Haskell does via candidates, specificity, `OVERLAPPABLE`/`OVERLAPPING`. I understand that there are differences how Haskell and Scala resolve instances, coherency etc. but I'm not sure which difference exactly is now important for you. – Dmytro Mitin Mar 05 '23 at 13:58
Actually, thank *you* for all the time and effort :) I don't see a `D`. You defined `A`, `B` and `C` and made it so that *all* `m` that are to be `B` *must* be `A` (which is not what I want). Scala line says *one* way of getting a `B m` is for `m` to be an `A` but if its not, then fine just ignore us (which is exactly what I want). Also the `instance A m => B m` line should not compile due to paterson-small rules (isolated, it gives the expected error but maybe in your code some Haskell magic is going on that I don't know but this is besides the point here). – Ashkan Kh. Nazary Mar 05 '23 at 14:19
"D is an instance of B but not of A" assuming you mean `C` here (there is no `D`) then no, your code does not allow this. The line `instance A m => B m` means any `m` that is `B` *must* be `A` as well. – Ashkan Kh. Nazary Mar 05 '23 at 14:21
See the few first lines of Daniel Wagner above – Ashkan Kh. Nazary Mar 05 '23 at 14:22
@AshkanKh.Nazary Excuse me, did you look at the code I linked? https://scastie.scala-lang.org/DmytroMitin/Nz1BZQwEQfu6HFQpzBKNww/7 https://ideone.com/iZtAyh I guess you missed a comment – Dmytro Mitin Mar 05 '23 at 14:23
@AshkanKh.Nazary I updated the answer as well – Dmytro Mitin Mar 05 '23 at 14:30
I missed your comment with the links. Yeah I see what you did there and it compiles. I'm not sure it is what it we think it means though . We can go step by step and try to figure this out if you are interested. Let's start here https://ideone.com/s3wZwd and tell me how you fix the error. – Ashkan Kh. Nazary Mar 05 '23 at 14:34
Oh I see you cheated with `UndecidableInstances` :D – Ashkan Kh. Nazary Mar 05 '23 at 14:37
2

@AshkanKh.Nazary `UndecidableInstances` has a scary name, but it's actually pretty harmless (the compiler uses a finite depth search, so even when it's not statically guaranteed for constraint resolution to finish it's still guaranteed not to get stuck in an infinite loop or anything). So the error your getting without `UndecidableInstances` is not really a major issue; the main problem is that you want a catch-all instance with a constraint **plus** additional single-type instances. – Ben Mar 05 '23 at 14:47
@ben I want *conditional* head selection rules to be applied based on which context is satisfied by `m` (https://stackoverflow.com/q/30249108/369489). So if an `m` is a `A` then pick `A => B` rule, otherwise just keep looking. I am lead to believe (mostly by you :D and Daniel above and people in IRC) that this is not possible (and for good reason which I partly understand). But Dmytro's code apparently does this impossible thing and compiles ! I'm wondering is this due to undecidable instances magic or did I get something wrong, again ? – Ashkan Kh. Nazary Mar 05 '23 at 15:17
@AshkanKh.Nazary `UndecidableInstances` is not actually cheating. Generally `instance A m => B m` is a recursion, for example concatenation of hlists https://scastie.scala-lang.org/DmytroMitin/nzuJPyNSTVmCzUii25cY8g/1 https://ideone.com/GZLF2X So `The constraint ‘A m’ is no smaller than the instance head` in your code means that the compiler can't guarantee that the recursion finishes but it still can finish. So I guess it's ok to switch on `UndecidableInstances`. – Dmytro Mitin Mar 05 '23 at 15:20
@AshkanKh.Nazary In Scala type classes are more flexible than in Haskell (or just different from Haskell). So in Scala you can do things out-of-the-box while standardized part of Haskell is quite restrictive so you should switch on some extensions. – Dmytro Mitin Mar 05 '23 at 15:23
1

@AshkanKh.Nazary What you're calling conditional selection is just another way of describing exactly the same thing. And no, the thing that makes Dmytro's code able to do that is the `{-# OVERLAPPING #-}`. I mentioned this in an earlier comment, but it's a somewhat advanced and "dangerous" feature, in that it has surprising corner cases and it breaks assumptions that a lot of existing code implicitly relies on. So to use it effectively you will need to understand it really well; that probably requires reading the GHC user's guide in detail, rather than just referencing a single example here. – Ben Mar 05 '23 at 15:26
@DmytroMitin I take it back. You understand what you are talking about, it is me who doesn't understand how overlapping instances work. – Ashkan Kh. Nazary Mar 05 '23 at 15:56
@Ben would you please take a look a my other question https://stackoverflow.com/q/75642815/369489 – Ashkan Kh. Nazary Mar 05 '23 at 15:57
@AshkanKh.Nazary https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/instances.html#overlapping-instances (6.8.8.5. Overlapping instances) – Dmytro Mitin Mar 05 '23 at 16:06
@AshkanKh.Nazary *"Eliminate any candidate for which there is another candidate such that both of the following hold: - is strictly more specific than . ... - is overlappable or is overlapping"* – Dmytro Mitin Mar 05 '23 at 16:17
@AshkanKh.Nazary I guess I understood what you meant to be possible in Scala with `implicit def fromA[M[_]: A]: B[M]` https://scastie.scala-lang.org/DmytroMitin/SpuuQYfqQZibQk6EiVQnHw and not possible in Haskell with `instance A m => B m` https://ideone.com/mXXug0 This is not fixable with `OVERLAPPING`/`OVERLAPPABLE`. I guess you can be interested in questions https://stackoverflow.com/questions/75493880 https://stackoverflow.com/questions/75182250 – Dmytro Mitin Mar 05 '23 at 17:28

How do I conditionally declare an instance?

3 Answers3

Linked