时间戳

首页 > 解决方案 > 如何在 SML 中使用 foldr 解析列表

sml - 如何在 SML 中使用 foldr 解析列表

问题描述

假设我有一个清单：

type myList = (string * int) list;

我想使用 foldr 找到这个列表的特定元素，比如：

fun findElement (element : string) (list : myList) : int result =
 if needed_element is equal current_list_element then return current_list_element
 else continue checking the rest of the list
 else return -1

我该怎么做呢？

标签： sml

解决方案

编写伪代码真的很有帮助。

明确确定此函数的类型也是非常有帮助的，例如：

val findElement = fn : string -> myList -> ?

函数应该返回什么类型？在您编写的伪代码int result中，但result不能作为标准 ML 中的内置类型构造函数使用。那么它应该是什么？int? 如果没有匹配的元素怎么办，您如何区分任何特定结果和“无结果”？你有什么选择？

尝试在不先使用的情况下解决此问题foldr。

由于扫描列表意味着沿其结构递归，因此您可以使用模式匹配编写此函数，其中您将模式分为一个匹配空列表和一个匹配非空列表：

fun lookup needle [] = ?
  | lookup needle ((key, value) :: haystack) =
      if ?
      then ?
      else ?
  • 条件必须needle与每一对的某些东西进行比较，直到匹配。您如何比较 SML 中的两个相等值？
  • 当条件满足时，不需要进行进一步的递归，所以可以返回一个值。如何在 SML 中返回一些东西？
  • 当条件不满足时，通过lookup调用自身继续搜索haystack。称自己是指lookup在“”之后的身体内部else。它应该用什么参数来调用自己？

了解基本的递归函数是理解的先决条件foldr。此时，请尝试阅读有关foldr. 我找不到任何专门针对此的好的开放材料，因此我会查找您可用的任何书本形式的学习材料。

就与表达相关的挑战lookup而言foldr：

  • foldr找到元素时不会停止递归。
  • 您可以通过抛出异常并捕获它来停止它。这有点棘手。
  • 您可以让它循环到最后并保留找到的第一个元素。这有点低效。

模板可能如下所示：

fun lookup needle haystack =
    foldr (fn ((key, value), acc) => ?) ? haystack

或者您可以在fn ... => ?本地命名匿名函数：

fun lookup needle haystack =
    let fun go ((key, value), acc) = ?
    in foldr go ? haystack
    end

这里?指的是lookup返回的类型的值。

无论您使用手动递归还是foldr.

推荐阅读