SML 定义简单数据结构 – 点对(CONS)和节点(NODE)

函数式具有抽象的数据结构,与硬件物理结构无关,而 CONS 源于 Lisp,在 SML 也有应用。

CONS

CONS 是构成 list 的基本元素,在 Lisp 里可以直接用于定义 list,在 SML 也可用于自定义 list。
定义以及简单使用 Demo:

(* generic type mylist *)
datatype 'element mylist = NIL
  | CONS of 'element * 'element mylist;

(* Simple usage *)
fun append NIL ys = ys
  | append(CONS(x, xs)) ys = CONS(x, append xs ys)

fun reverse NIL = NIL
  | reverse(CONS(x, xs)) = append (reverse xs) (CONS(x, NIL))

val L = CONS(2, CONS(0, CONS(1, CONS(8, NIL))))
(* -> val L = CONS (2, CONS (0, CONS (1, CONS (8, NIL)))): int mylist *)

val L = append L (CONS(4, NIL));
(* -> val L = CONS (2, CONS (0, CONS (1, CONS (8, CONS (4, ...))))): int mylist *)

reverse L;
(* -> val it = CONS (4, CONS (8, CONS (1, CONS (0, CONS (2, ...))))): int mylist *)

NODE

NODE 只是一个标识,也可用其他名称,在 SML 中定义树可采用 NODE。

(* generic type tree *)
datatype 'element tree = Empty
  | NODE of 'element tree * 'element * 'element tree;

(* Simple usage *)
fun list_to_tree ([]) = Empty
  | list_to_tree (t)  = let
    fun split []        = ( [],  [], [])
      | split [x]       = ( [], [x], [])
      | split [x, y]    = ([x], [y], [])
      | split (x::y::L) = let
        val (L, M, R)   = split L
      in
        (x::L, M, y::R)
    end

    val (L, x, R) = split(t)
  in
    NODE (list_to_tree L, x, list_to_tree R)
  end;

list_to_tree [1, 2, 3, 4];
(* ->
val it =
   NODE
    (NODE (NODE (Empty, [1], Empty), [3], Empty), [4],
     NODE (Empty, [2], Empty)): int list tree
*)

参考:

  1. https://en.wikipedia.org/wiki/Cons

作者: YanWen

Web 开发者

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s