koka-lang / koka

Koka language compiler and interpreter
http://koka-lang.org
Other
3.3k stars 167 forks source link

Nested generic type seems to lose information when pattern matching #603

Closed Caid11 closed 3 hours ago

Caid11 commented 4 hours ago

This code fails to compile:

type mapMember<k,v>
  Unoccupied
  Occupied(key: k, value: v)

pub struct arrayBackedMap<k,v>
  hashFunc : k -> int
  keyCmp : (k,k) -> bool
  members: vector<mapMember<k,v>>

pub fun map-with-key(m : arrayBackedMap<k,v>, f : (k, v) -> a) : arrayBackedMap<k,a>
  fun fm(member : mapMember<k,v>) : mapMember<k,a>
    match member
      Unoccupied -> Unoccupied
      Occupied(km, vm) ->
        Occupied(km, f(km, vm))

  val new-members : vector<mapMember<k,a>> = m.members.map(fm)
  m(members = new-members)

...with this error message:

main.kk(15,22): type error: abstract types do not match
  context      :                      f(km, vm)
  term         :                      f(km, vm)
  inferred type: $b
  expected type: $a
  because      : type cannot be instantiated to match the annotation

Failed to compile main.kk

It feels like this should work, given that arrayBackedMap<k,v> specifies that members is a vector of mapMember<k,v>.

My configuration's details:

Caid11 commented 3 hours ago

This version works:

type mapMember<k,v>
  Unoccupied
  Occupied(key: k, value: v)

pub struct arrayBackedMap<k,v>
  hashFunc : k -> int
  keyCmp : (k,k) -> bool
  members: vector<mapMember<k,v>>

pub fun map-with-key(m: arrayBackedMap<k,v>, f : (k,v) -> e a) : e arrayBackedMap<k,a>
  val new-mems = m.members.map(fn(mem)
    match mem
      Unoccupied -> Unoccupied
      Occupied(ka,va) -> Occupied(ka, f(ka,va))
  )
  ArrayBackedMap(m.hashFunc, m.keyCmp, new-mems)

pub fun main()
  ()

I believe the problem was that the initial version used m(members = new-members) to create a new map, which expects members to be mapMember<k,v>. I needed to create a map with mapMember<k,a>, so I had to switch it to ArrayBackedMap(m.hashFunc, m.keyCmp, new-mems).