SML续体传递风格实现迭代时的循环性类型错误排查

尝试用续体（continuations）实现字符串迭代，编写了以下SML代码：

fun stringChars string =
    let val len = size string
    fun nextChar index kEndOfString kReadChar =
        if len = index
        then kEndOfString ()
        else kReadChar(index, String.sub(string, index), nextChar (index + 1))
    in nextChar 0
    end

但出现循环性类型错误：

Error: right-hand-side of clause does not agree with function result type [circularity]
  expression:  (unit -> 'Z) -> (int * char * 'Y -> 'Z) -> 'Z
  result type:  'Y
  in declaration:
    nextChar =
      (fn arg =>
            (fn arg =>
                  (fn arg =>
                        (case (arg,arg,arg)
                        of (<pat>,<pat>,<pat>) =>
                             if <exp> then <exp> else <exp>))))
val it = () : unit

stringChars的设计意图是返回一个接收两个续体的函数：一个处理字符串遍历结束，一个处理单个字符。期望通过以下collect函数收集字符为列表：

fun collect stream =
    let fun iter stream results =
            stream (fn () => rev results)
                   (fn (index, char, stream) => iter stream (char::results))
    in iter stream []
    end

例如调用collect (stringChars "Hello")应返回[#"H", #"e", #"l", #"l", #"o"]，但collect同样无法通过类型检查：

Error: case object and rules do not agree [circularity]
  rule domain: ((unit -> 'Z list) -> ('Y * 'Z * 'X -> 'W) -> 'V) * 'Z list
  object: 'X * 'U
  in expression:
    (case (arg,arg)
    of (stream,results) =>
         (stream (fn () => rev results))
           (fn (index,char,stream) => (iter stream) (char :: results)))
val it = () : unit

手动指定类型时会出现循环依赖问题：nextChar的类型依赖kReadChar的类型，而kReadChar的类型又依赖nextChar的类型。以下是可运行的Common Lisp实现示例：

(defun string-chars (string)
  (let ((length (length string)))
    (labels ((next-char (index k-end-of-string k-read-char)
               (if (= index length)
                   (funcall k-end-of-string)
                   (funcall k-read-char 
                            index 
                            (aref string index) 
                            (lambda (k-end-of-string k-read-char)
                              (next-char (1+ index) k-end-of-string k-read-char))))))
      (lambda (k-end-of-string k-read-char)
        (next-char 0 k-end-of-string k-read-char)))))

(defun collect (stream)
  (labels ((iter (stream result)
             (funcall stream
                      (lambda () (reverse result))
                      (lambda (index char stream)
                        (declare (ignore index))
                        (iter stream (cons char result))))))
    (iter stream '())))

(collect (string-chars "Hello"))
;; '(#\H #\e #\l #\l #\o)

请问是否存在可通过SML类型检查的实现方案？

SML的静态类型系统无法自动推导代码中隐含的递归类型依赖，需要显式声明递归类型来解决循环性错误。以下提供两种可行方案：

方案一：使用递归类型别名 #

先定义一个递归的'a stream类型，明确stream是接收两个续体的函数，其中第二个续体的参数包含下一个stream：

type 'a stream = (unit -> 'a) -> (int * char * 'a stream -> 'a) -> 'a

然后修改stringChars和collect函数，指定类型让编译器识别递归依赖：

fun stringChars (string: string): 'a stream =
    let val len = size string
    fun nextChar (index: int): 'a stream =
        fn kEndOfString => fn kReadChar =>
            if len = index
            then kEndOfString ()
            else kReadChar(index, String.sub(string, index), nextChar (index + 1))
    in nextChar 0
    end

fun collect (stream: 'a stream): char list =
    let fun iter (s: 'a stream) (results: char list): 'a =
            s (fn () => rev results)
               (fn (_, char, next_s) => iter next_s (char::results))
    in iter stream []
    end

调用collect (stringChars "Hello")会返回预期的[#"H", #"e", #"l", #"l", #"o"]。

方案二：使用递归数据类型封装 #

用datatype显式定义递归的stream结构，让编译器能直接识别递归关系：

datatype 'a stream = Stream of (unit -> 'a) -> (int * char * 'a stream -> 'a) -> 'a

fun stringChars string =
    let val len = size string
    fun nextChar index =
        Stream (fn kEndOfString => fn kReadChar =>
            if len = index
            then kEndOfString ()
            else kReadChar(index, String.sub(string, index), nextChar (index + 1)))
    in nextChar 0
    end

fun collect (Stream stream) =
    let fun iter (Stream s) results =
            s (fn () => rev results)
               (fn (_, char, next_stream) => iter next_stream (char::results))
    in iter (Stream stream) []
    end

这个方案通过Stream构造器封装续体函数，避免了直接的函数类型递归推导问题，同样能通过类型检查并正常工作。

原代码报错原因 #

原代码中，nextChar返回的函数依赖kReadChar的类型，而kReadChar又接收nextChar的返回值作为参数，形成了隐含的递归类型依赖。SML的类型推导器无法自动解析这种循环依赖，必须通过显式声明递归类型（类型别名或数据类型）来告知编译器类型的递归结构。

内容的提问来源于stack exchange，提问作者chebert