google-research / google-research/dex-lang

Overlapping/default type class instances

Open
#340 7 comments 0 reactions 0 assignees View on GitHub
language / concrete syntax
Dominant language
Haskell
Stars
1.7k
Forks
116
PR merge metrics
No merged PRs in 30d

Description

Continuing with from #339

If i have a type-class
```
data Hashable a:Type = MkHashable (a->a->Bool) (Int->a->Int) -- isequal, hash
```

and I define a instance of it for `Int32`
```
@instance Int32Hashable : Hashable Int32 = (MkHashable
(\a b. a==b)
(\seed x. I64ToI $ hash (IToI64 seed) x)
)
```

and also a generic fallback defintion that work on anything that has `Eq`:
```
@instance FallbackHashable : Eq t ?=> Hashable t = (MkHashable
(\a b. a==b)
(\seed x. 1) -- performance degrades to O(n) search 🤷
)
```

and then i try and use this:
```
tryfindlast : (Hashable a) ?=> (n=>a)->a->(Maybe n) = \col val.
fold Nothing \i state.
select (col.i `isequal` val) (Just i) state

:p tryfindlast [1,2,3,2,3,4] 3
```
I get an error:
```
Type error:Multiple candidate class dictionaries for: (Hashable Int32)
```

I expected that it would chose the most specific instance.
Which I think loosely can be defined as the one with the fewest things on the left of the `?=>`.

it seems like being able to this would be useful so on can define general ways of doing things as well as optimized special cases.

Contributor guide

Open the contributing guide

Research direction

No file, test, or entry point is named in the issue. Start by locating the type-class instance resolution code and reproduce the Int32 example with both the specific and Eq-constrained fallback instances; done means the specific instance is selected deterministically, while ambiguous cases still report an error.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.