FStarLang / FStarLang/FStar

Type abbreviation causes problems with dropping part of a refinement of a list element

Open
#2,102 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
F*
Stars
3.1k
Forks
266
Avg merge
21h 1m
Merged PRs (30d)
54

Description

I couldn't think of a good name for the issue. The code below doesn't typecheck after replacing a type written directly (a list with refinement on it's item) with a type abbreviation.
```
type item =
| Mkitem : _field1:option string -> _field2:option nat -> _field3: option bool -> item

type item_with_field1_and_field2 = x:item{Some? x._field1 /\ Some? x._field2}

val list_weaken : #a:Type -> #p:(a->Type0) -> #q:(a->Type0) -> list (x:a{p x /\ q x}) -> Tot (list (z:a{p z}))
let rec list_weaken #a #p #q l =
match l with
| [] -> []
| x::xs -> x :: list_weaken #a #p #q xs

let testWorks (l : list (x:item{Some? x._field1 /\ Some? x._field2}) : list (it:item{Some? it._field1}) = list_weaken l
let testFails (l : list item_with_field1_and_field2) : list (it:item{Some? it._field1}) = list_weaken l

// workaround is to provide explicit instantiation
let testWorks2 (l : list item_with_field1_and_field2) : list (it:item{Some? it._field1}) = list_weaken #_ #_ #(fun x -> Some? x._field2) l
```

Contributor guide

Open the contributing guide

Research direction

Start with the minimal reproducer in the issue and compare typechecking of the direct refinement with the type abbreviation. Verify the behavior against the explicit-instantiation workaround. Done means the abbreviated-type call typechecks without requiring the explicit instantiation, while the existing examples remain valid.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.