[racket] for*/list and Typed Racket

On Tue, Jun 26, 2012 at 7:26 AM, Adolfo Pérez Álvarez
<adolfo.pa at gmail.com> wrote:
> Hi All,
>
> It seems that the problem is in for*/list: itself. For example, the
> following code fails to typecheck, but I don't see anything wrong with
> it:
>
> #lang typed/racket
>
> (for*/list: ([a : Number '(1 2 3)]
>             [b : Number '(4 5 6)])
>  (+ a b))
>
> Any idea of why doesn't typecheck? I'm totally lost now ...

Looking at this smaller example, I think that the nested recursion in
expansion of `for*/list` is confusing Typed Racket.  I'll look into
why that is, and if it can be fixed.  In the meantime, you ought to be
able to rewrite the loop to use `for/fold:` and `reverse` to work
around this issue.

Sam

>
> Thanks.
> 2012/6/25 Adolfo Pérez Álvarez <adolfo.pa at gmail.com>:
>> Oh my ... I mis-annotated the code *again* :-(
>>
>> Here is the corrected definition of colorize:
>>
>> (: colorize : Map (Listof Color) -> (Listof Solution))
>> (define (colorize map colors)
>>  (for/fold: ([solutions : (Listof Solution) empty-solution]) ([entry
>> : Map map])
>>    (match-let ([(cons region neighbours) entry])
>>      (for*/list: ([s : Solution solutions]
>>                   [c : Color colors]
>>                   #:when (not (findf (λ: ([rc : (Pair Region Color)])
>>                                        (and (memv (car rc) neighbours)
>>                                             (eqv? (cdr rc) c)))
>>                                      s)) )
>>        (cons (cons region c) s)))))
>>
>> 2012/6/25 Adolfo Pérez Álvarez <adolfo.pa at gmail.com>:
>>> Thanks a lot for your answer, Sam. It seems I completely missed the
>>> for/xxx: forms while looking up the documentation.
>>>
>>>> One, as the error message said, Typed Racket needed more help in the
>>>> form of annotations to check your program. Two, you were using
>>>> `for*/list` as if it was `for*/fold`.  Unfortunately, the
>>>
>>> Sorry to inform you that your version doesn't work as expected ;-) I
>>> use for*/list to generate 'n' new partial solutions for each one of
>>> the  's'  generated by the outer for/fold for each color (it's is a
>>> quick and dirty solution to the map coloring problem). So the inner
>>> for/fold: doesn't do the trick :-).
>>>
>>> Anyway, I got the type annotations completely wrong ... by mistake I
>>> defined a set of solutions as a (Listof (Pair Region Color)) instead
>>> of a (Listof (Listof (Pair Region Color))). Also, I should have called
>>> "empty-solution" "empty-solutions" or "empty-solution-set" instead.
>>>
>>> Now I've tried to use for*/list:, annotating the bindings (correctly I
>>> hope), but still doesn't work. It fails (again) with the same error
>>> message:
>>>
>>> Type Checker: Error in macro expansion -- insufficient type
>>> information to typecheck. please add more type annotations in:
>>> (for*/list: ((s : (Listof (Pair Region Color)) solutions) (c : (Listof
>>> Color) colors) #:when (not (findf (λ: ((rc : (Pair Region Color)))
>>> (and (memv (car rc) neighbours) (eqv? (cdr rc) c))) s))) (cons (cons
>>> region c) s))
>>>
>>> To make things a little clearer I've added a new type "Solution"; now
>>> the code looks like this:
>>>
>>> #lang typed/racket
>>>
>>> (define-type Region Number)
>>> (define-type Color Number)
>>> (define-type Solution (Listof (Pair Region Color)))
>>>
>>> (: empty-solution : (Listof Solution))
>>> (define empty-solution '(()))
>>>
>>> (define-type Map (Listof (Pair Region (List Region))))
>>>
>>> (: colorize : Map (Listof Color) -> (Listof Solution))
>>> (define (colorize map colors)
>>>  (for/fold: ([solutions : (Listof Solution) empty-solution]) ([entry
>>> : Map map])
>>>    (match-let ([(cons region neighbours) entry])
>>>      (for*/list: ([s : Solution solutions]
>>>                   [c : (Listof Color) colors]
>>>                   #:when (not (findf (λ: ([rc : (Pair Region Color)])
>>>                                        (and (memv (car rc) neighbours)
>>>                                             (eqv? (cdr rc) c)))
>>>                                      s)) )
>>>        (cons (cons region c) s)))))
>>>
>>> And again, thanks a lot for your answer.