ZipWith in Typed Racket, with Multiple Lists

Question

I've been practicing some with Typed Racket Scheme (this is my first month or so using Scheme), and I'm trying to rewrite the ZipWith function using types, and it's proving far more difficult that I thought.

Here is the untyped ZipWith I made and am trying to convert, very simple:

(define (zipwith fn . lists)
  (apply map fn lists))

Here is my attempt at the typed version. I tried looking at the types for map and apply to try to figure it out some, but I haven't had any luck with it so far:

(: zip-with (All (c a b ...) (-> (-> a b ... b c) (Listof b) ... b (Listof c))))
(define (zip-with fn . lists)
  (apply (inst map c a b ... b) fn lists))

The Dr Racket REPL I'm using gives me this error:

Type Checker: Bad arguments to function in `apply':
Domains: (-> a b ... b c) (Listof a) (Listof b) ... b
         (-> a c) (Pairof a (Listof a))
Arguments: (-> a b ... b c) (List (Listof b) ... b) *
 in: (apply (inst map c a b ... b) fn lists)

I see it complains about the apply function, but are my expected types correct otherwise? I could use some advice on how the completely translate my untyped version.

Ideally, I'd like the typed version to behave as closely to the untyped as possible, so I can do something like this (an example output using the untyped version):

> (zipwith list '(1 2 3) '(4 5 6) '(7 8 9))
'((1 4 7) (2 5 8) (3 6 9))

Edit: I did manage a version like Haskell's, just copying the type signature as-is essentially. It is:

(: zip-with2 (All (a b c) (-> (-> a b c) (Listof a) (Listof b) (Listof c))))
(define (zip-with2 fn list1 list2)
  (map fn list1 list2))

Although it's trickier to call than I would like (I had to use inst on the functions I tried, cons and list).

It’s worth pointing out that zip-with in Racket/Scheme is just map, and indeed, your implementation just forwards all of its arguments to map. Therefore, the type signature will be identical to map. — Alexis King
@AlexisKing Thanks, I didn't see that before! You're right, the signature of zipwith should be identical to map, since it's taking the same exact arguments. Adding apply to the mix made this fact harder to see at first. — user1017523

Alex Knauth Alex Knauth · Accepted Answer · 2016-06-18T20:52:21

As Alexis King already pointed out, zip-with is exactly map in racket, and its type signature should be the same. The type of map is

> (:print-type map)
(All (c a b ...)
  (case->
   (-> (-> a c) (Pairof a (Listof a)) (Pairof c (Listof c)))
   (-> (-> a b ... b c) (Listof a) (Listof b) ... b (Listof c))))

Looking at just the multi-list case, it's this:

(All (c a b ...)
  (-> (-> a b ... b c) (Listof a) (Listof b) ... b (Listof c)))

But the type you wrote was this:

(All (c a b ...)
  (-> (-> a b ... b c) (Listof b) ... b (Listof c)))

The fn function takes an a as the first argument, but there's no corresponding (Listof a) argument in the type you wrote.

Even the generalized multi-arg version of map/zip-with needs at least one list to work with, which is why the (Listof a) is necessary. That's also why instead of

(define (zip-with fn . lists)
  (apply map fn lists))

You need

(define (zip-with fn list1 . lists)
  (apply map fn list1 lists))

With those two changes, your code works:

#lang typed/racket

(: zip-with : (All (c a b ...) (-> (-> a b ... b c) (Listof a) (Listof b) ... b (Listof c))))
(define (zip-with fn list1 . lists)
  (apply (inst map c a b ... b) fn list1 lists))

It even works without the inst form:

(: zip-with : (All (c a b ...) (-> (-> a b ... b c) (Listof a) (Listof b) ... b (Listof c))))
(define (zip-with fn list1 . lists)
  (apply map fn list1 lists))

And since zip-with and map are the same thing anyway:

(: zip-with : (All (c a b ...) (-> (-> a b ... b c) (Listof a) (Listof b) ... b (Listof c))))
(define zip-with map)

Even though they're the same value, the advantage to this is that the type looks slightly simpler, with only the multi-list case.

ZipWith in Typed Racket, with Multiple Lists

1 Answers