如何让我的代码在 SML 中更加模块化？

Question

我正在使用 SML 进行编程。我的函数接受一个整数，然后用逗号将其拼接到一个列表中。例如数字 12345 -> [1,2.3,4,5]。我的问题是如何使我的代码更加模块化。我对我的代码进行了硬编码。我希望它能够处理无限数量的整数。

fun digits(m:int) =
  if m <10 then
    [m]
  else if m < 100 then
    [m div 10] @ [m mod 10]
  else if m > 100 andalso m < 1000 then
    [(m div 10) div 10] @[(m div 10) mod 10] @ [m mod 10]
  else if m > 1000 andalso m < 10000 then
    [((m div 10) div 10) div 10] @ [((m div 10) div 10) mod 10] @ [(m div 10) mod 10] @ [m mod 10]
  else if m > 10000 andalso m < 100000 then
    [(((m div 10) div 10) div 10) div 10] @ [((m div 10) div 10) div 10 mod 10] @ [((m div 10) div 10) mod 10] @ [(m div 10) mod 10] @ [m mod 10]
  else if m > 100000 andalso m < 1000000 then
    [((((m div 10) div 10) div 10) div 10) div 10] @ [(((((m div 10) div 10) div 10) div 10) mod 10) mod 10] @ [((m div 10) div 10) div 10 mod 10] @ [((m div 10) div 10) mod 10] @ [(m div 10) mod 10] @ [m mod 10]
  else if m > 1000000 andalso m < 10000000 then
    [(((m div 10) div 10) div 10) div 10 div 10 div 10] @ [(((m div 10) div 10) div 10) div 10 div 10 mod 10] @ [((m div 10) div 10) div 10 mod 10]@ [((m div 10) div 10) mod 10] @ [(m div 10) mod 10] @ [m mod 10]                                               
  else
    [(m div 10) div 10] @ [(m div 10) mod 10] @ [m mod 10]

Answer 1

考虑一下您要解决的问题。您无法对所有可能性进行硬编码。

让我们考虑一个基本示例：一位数字。显然，对于任何小于 10 的输入，结果就是列表中的数字。

fun digits m =
  if m < 10 then
    [m]

如果数字大于10，则可以是两位数，也可以更多。我们不知道。但我们能找到最小的数字吗？

fun smallestDigit m =
  if m < 10 then
    m
  else
    m mod 10

因此，如果我们调用

smallestDigit 123

，我们会得到

3

。

如果我们

123 div 10

，我们就会得到

12

。结果是，如果我们调用

2

，我们会得到

smallestDigit 12

。我们只需重复此操作，直到获得所有数字。在函数式编程中，这种重复通常是通过递归来实现的。

那么让我们使用递归将它们组合在一起。关键是我们有一个停止递归的退出条件，并且其他情况向该退出条件收敛。

fun digits m =
  if m < 10 then
    [m]
  else 
    let
      val smallestDigit = m mod 10
      val remainingDigits = m div 10
    in
      digits remainingDigits @ [smallestDigit]
    end

为了提高效率，我们可以使用

::

代替带有累加器的

@

。

虽然下面实现了使函数尾递归的目标，但整数不会大到足以导致堆栈溢出成为真正的问题。更重要的是，这避免了重复调用

@

，这会给前面的示例带来 O(n^2) 运行时复杂度，而不是产生 O(n) 运行时复杂度。

fun digits(n) =
  let 
    fun digits'(n, acc) =
      if n < 10 then n::acc
      else digits'(n div 10, (n mod 10)::acc)
  in
    digits'(n, [])
  end;