时间戳

首页 > 解决方案 > SML使用reduce和map遍历n叉树

tree - SML使用reduce和map遍历n叉树

问题描述

我是 SML 的新手。

假设我有以下数据类型：

datatype 'a tree = leaf of 'a | node of 'a tree list

和功能val leaves = fn : 'a tree -> 'a list：

fun leaves (leaf x) = [x]
  | leaves (node []) = []
  | leaves (node [x]) = leaves x
  | leaves (node (x::xs)) = (leaves x) @ (leaves (node xs))

如果我有

val t = node [node [leaf 1,
              node [leaf 2, leaf 3],
              leaf 4]];

然后，leaves t会回来[1, 2, 3, 4]找我。

我想问的是，这可以用reduceand重写map吗？

鉴于减少：

fun reduce g [x] = x
  | reduce g (x::xs) = (g x (reduce g xs))

非常感谢。

标签： treesml

解决方案

您似乎有一个反复出现的模式，即从太多子句开始。

从两个必要的开始：

fun leaves (leaf x) = [x]
  | leaves (node xs) = ???

现在，xs是一个列表。
map将列表转换为不同的列表。
reduce将列表简化为单个值。

这表明你想要某种形式的东西

| leaves (node xs) = reduce f (map g xs)

确定f并g离开作为练习。

推荐阅读