Typed Racket 中的 ZipWith，带有多个列表

Question

我一直在使用 Typed Racket Scheme 进行一些练习（这是我使用 Scheme 的第一个月左右），我正在尝试使用类型重写 ZipWith 函数，事实证明它比我想象的要困难得多。

这是我制作并正在尝试转换的无类型 ZipWith，非常简单：

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

这是我对打字版本的尝试。我试着查看 map 和 apply 的类型，试图弄清楚一些，但到目前为止我还没有找到任何运气：

(: 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))

我正在使用的 Dr Racket REPL 给我这个错误：

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)

我看到它抱怨 apply 函数，但我预期的类型是否正确？我可以使用一些关于如何完全翻译我的无类型版本的建议。

理想情况下，我希望类型化版本的行为尽可能接近非类型化版本，因此我可以这样做（使用非类型化版本的示例输出）：

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

编辑： 我确实管理过类似 Haskell 的版本，基本上只是按原样复制类型签名。它是：

(: 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))

虽然调用起来比我想要的要复杂（我不得不在我尝试的函数上使用 inst，cons 和 list）。

Answer 1

正如 Alexis King 已经指出的那样，zip-with 在 racket 中正好是 map，并且其类型签名应该相同。地图类型是

> (: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))))

只看多列表的情况，是这样的：

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

但是你写的类型是这样的：

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

fn 函数将 a 作为第一个参数，但在您编写的类型中没有对应的 (Listof a) 参数。

即使是 map/zip-with 的广义多参数版本也需要至少一个列表才能使用，这就是为什么需要 (Listof a) 的原因。这也是为什么不用

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

你需要

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

通过这两项更改，您的代码有效：

#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))

它甚至可以在没有 inst 形式的情况下工作：

(: 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))

因为 zip-with 和 map 无论如何都是一回事：

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

即使它们是相同的值，这样做的好处是类型看起来稍微简单一些，只有多列表的情况。

Typed Racket 中的 ZipWith，带有多个列表

ZipWith in Typed Racket, with Multiple Lists

types

racket

typed-racket