时间戳

首页 > 解决方案 > SML：LookSay 递归

recursion - SML：LookSay 递归

问题描述

我正在自学函数式编程，没有老师可以指导我。谢谢你帮助我！

(*lookSay:int list=>int*int list
ENSURE: true
REQUIRE: computes the look-and-say sequence, for example list of l=[2,2,2] which would be read as "three twos"  =>[(2,1),(1,2)] *)

这是我的代码：

    fun lookSay(x:int list)=
    case x of
    []=>[]
      | l::ls =>
    let fun helper(l,l'::ls',acc)=
              if l=l'
              then helper(l,ls',acc+1)
              else (acc,l)::lookSay(ls)
    in
        helper(l,ls,1)
    end

我不明白为什么它不起作用。其他人提供的解决方案是使用辅助函数 runWith(x,L) 返回 (repeated, tail) ：但我不知道如何得出这个解决方案..

    fun runWith (_:int, [] : int list) : int list * int list = ([], [])
  | runWith (x, y::L) =
    if x = y then
      let
        val (repeats, tail) = runWith(x, L)
      in
        (x::repeats, tail)
      end
    else
      ([], y::L)

标签： recursionsml

解决方案

我将首先像这样格式化您的解决方案：

fun lookSay [] = []
  | lookSay (x::xs) =
    let
      fun helper(y, z::zs, count) =
          if y = z
          then helper(y, zs, count + 1)
          else (count, y) :: lookSay zs
    in
      helper(x, xs, 1)
    end

我使用x,y而z不是landl'因为我发现它l很难阅读：我无法轻易看出它是小写 L、大写 i 还是 1。因为我们实际上也在使用常量 1，这增加了混乱。

我还做了一些变量重命名：在 case-of 的范围内有一对land ，在辅助函数内部有另一对同名的and来隐藏外部变量。虽然这是可行的，但将不同的事物命名为相同的名称非常令人困惑。lslls

同样，我重命名acc为count以澄清它累积的内容。

正如 molbdnilo 暗示的那样，您的问题在于缺少模式匹配。ML 编译器应该警告您：

! Toplevel input:
! ..........helper(y, z::zs, count) =
!           if y = z
!           then helper(y, zs, count + 1)
!           else (count, y) :: lookSay zs
! Warning: pattern matching is not exhaustive

哪些提示也helper应该有一个[]模式。

至于这个解决方案的策略：内部helper函数做了两件事，需要一个内部辅助函数。首先，它有一个关于“当前”项目的额外参数，我称之为y，其次，它有一个累积参数，我称之为count。特殊的是，helper调用lookSay而不是自身。

但其中只有第二个是真正必要的，因为您还可以使用列表参数的头部来保留“当前”项目：

fun lookSay xs =
  let
    fun go [] _ = []
      | go (x::y::zs) count =
        if x = y
        then go (x::zs) (count + 1)
        else (count + 1, x) :: go (y::zs) 0
  in
    go xs 0
  end

此策略一次查看列表的前两个元素，x和y，如果它们相等，则丢弃一个但递增count。如果x和y不相等，则这标志着xs 序列的结束，因此(count + 1, x)发出一个元素并且go可以在 上递归调用自身y::zs。

我保留了您的示例中也存在的错误。在我的版本中，molbdnilo 的提示可以改写为“想想go函数如何处理只有一个元素的列表”。

我认为为了让这个函数更有用，你实际上想要发出一个简单的列表：

fun concatMap f xs =
    List.concat (List.map f xs)

fun flatten pairs =
    concatMap (fn (n, x) => [n, x]) pairs

fun lookSay xs =
  let
    fun go [] _ = []
      | go (x::y::zs) i =
        if x = y
        then go (x::zs) (i+1)
        else (i+1,x) :: go (y::zs) 0
  in flatten (go xs 0) end

假设错误得到修复，这应该给你：

- lookSay [1, 1, 1, 2, 2, 3];
> val it = [3, 1, 2, 2, 1, 3] : int list

推荐阅读