具有惰性列表功能的 SML
SML with lazy list function
我正在尝试制作一个可以 return lazylist 的特定第 n 个元素的函数。
这是我做的:
datatype 'a lazyList = nullList
| cons of 'a * (unit -> 'a lazyList)
fun Nth(lazyListVal, n) = (* lazyList * int -> 'a option *)
let fun iterator (laztListVal, cur, target) =
case lazyListVal of
nullList => NONE
| cons(value, tail) => if cur = target
then SOME value
else iterator (tail(), cur+1, target)
in
iterator(lazyListVal,1,n)
end
我预期的结果是,随着回收的进行,最终变量 cur
与变量 target
[=32 相同=],然后是函数迭代器 returns SOME value
所以它将 return 最后的第 n 个元素。
但是当我编译它并 运行 时,它只是 return 的第一个元素,但是我用 lazylist 对象进行了测试。
请找出问题所在。我不知道...
cf) 我制作了另一个与此问题相关的函数,该函数将 lazylist 转换为包含前 N 个值的 SML 原始列表。以上代码:
fun firstN (lazyListVal, n) = (* lazyList * int -> 'a list *)
let fun iterator (lazyListVal, cur, last) =
case lazyListVal of
nullList => []
| cons(value, tail) => if cur = last
then []
else value::iterator(tail(),cur+1,last)
in
iterator(lazyListVal,0,n)
end
奇怪的是 firstN 函数正常工作。
问题是您的 iterator
函数执行 case lazyListVal of ...
,但递归尾部调用 laztListVal
,因此对于每次迭代,它一直在查看第一个列表。使用更好的变量名来避免这种 "invisible" 错误。
nth
的更简单定义:
datatype 'a lazyList = NullList | Cons of 'a * (unit -> 'a lazyList)
fun nth (NullList, _) = NONE
| nth (Cons (x, xs), 0) = SOME x
| nth (Cons (_, xs), n) = nth (xs (), n-1)
val nats = let fun nat n = Cons (n, fn () => nat (n+1)) in nat 0 end
val ten = nth (nats, 10)
编辑: 虽然函数模式匹配在这里很理想,但您也可以使用 case ...的... 在这里。但是,辅助函数似乎是不必要的,因为您可以简单地使用输入参数 n
作为迭代器:
fun nth (L, n) =
case (L, n) of
(NullList, _) => NONE
| (Cons (x, xs), 0) => SOME x
| (Cons (_, xs), n) => nth (xs (), n-1)
然而,您可能希望使该功能更强大:
fun nth (L, n) =
let fun nth' (NullList, _) = NONE
| nth' (Cons (x, xs), 0) = SOME x
| nth' (Cons (_, xs), n) = nth' (xs (), n-1)
in if n < 0 then NONE else nth' (L, n) end
这里有一个辅助函数确保 n < 0
只检查一次。
(您也可以 raise Domain
,因为负指数不是 well-defined。)
我正在尝试制作一个可以 return lazylist 的特定第 n 个元素的函数。
这是我做的:
datatype 'a lazyList = nullList
| cons of 'a * (unit -> 'a lazyList)
fun Nth(lazyListVal, n) = (* lazyList * int -> 'a option *)
let fun iterator (laztListVal, cur, target) =
case lazyListVal of
nullList => NONE
| cons(value, tail) => if cur = target
then SOME value
else iterator (tail(), cur+1, target)
in
iterator(lazyListVal,1,n)
end
我预期的结果是,随着回收的进行,最终变量 cur
与变量 target
[=32 相同=],然后是函数迭代器 returns SOME value
所以它将 return 最后的第 n 个元素。
但是当我编译它并 运行 时,它只是 return 的第一个元素,但是我用 lazylist 对象进行了测试。
请找出问题所在。我不知道...
cf) 我制作了另一个与此问题相关的函数,该函数将 lazylist 转换为包含前 N 个值的 SML 原始列表。以上代码:
fun firstN (lazyListVal, n) = (* lazyList * int -> 'a list *)
let fun iterator (lazyListVal, cur, last) =
case lazyListVal of
nullList => []
| cons(value, tail) => if cur = last
then []
else value::iterator(tail(),cur+1,last)
in
iterator(lazyListVal,0,n)
end
奇怪的是 firstN 函数正常工作。
问题是您的 iterator
函数执行 case lazyListVal of ...
,但递归尾部调用 laztListVal
,因此对于每次迭代,它一直在查看第一个列表。使用更好的变量名来避免这种 "invisible" 错误。
nth
的更简单定义:
datatype 'a lazyList = NullList | Cons of 'a * (unit -> 'a lazyList)
fun nth (NullList, _) = NONE
| nth (Cons (x, xs), 0) = SOME x
| nth (Cons (_, xs), n) = nth (xs (), n-1)
val nats = let fun nat n = Cons (n, fn () => nat (n+1)) in nat 0 end
val ten = nth (nats, 10)
编辑: 虽然函数模式匹配在这里很理想,但您也可以使用 case ...的... 在这里。但是,辅助函数似乎是不必要的,因为您可以简单地使用输入参数 n
作为迭代器:
fun nth (L, n) =
case (L, n) of
(NullList, _) => NONE
| (Cons (x, xs), 0) => SOME x
| (Cons (_, xs), n) => nth (xs (), n-1)
然而,您可能希望使该功能更强大:
fun nth (L, n) =
let fun nth' (NullList, _) = NONE
| nth' (Cons (x, xs), 0) = SOME x
| nth' (Cons (_, xs), n) = nth' (xs (), n-1)
in if n < 0 then NONE else nth' (L, n) end
这里有一个辅助函数确保 n < 0
只检查一次。
(您也可以 raise Domain
,因为负指数不是 well-defined。)