標籤：

函數式編程語言該如何表示樹結構呢？

01-11

比如在Erlang、Scala、Kotlin里通常是如何表示一個樹結構的呢？

慣用法是利用類似list這樣的類型嗎？

在函數式語言中，樹之類的遞歸數據結構大概有這些表示方法：

  • 用普通的algebraic data type遞歸地表示。如果語言支持GADT甚至inductive families的話，可以在類型里表達更強的性質來約束樹結構，比如規定所有子樹等高之類
  • 用某個base functor的不動點表示（Data types à la carte ）
  • 用衍生自某個functor的free monad表示，比如list的free monad用來表示rose tree
  • 不使用data type，只使用普通的函數來表示，也就是所謂的encoding。常見的有Mogensen-Scott encoding或者Boehm-Berarducci encoding

歸根到底，你只需要兩樣東西：1. 構造一棵樹的方法 2. 在這棵樹上進行某種運算的方法。以上手段都可滿足

另外值得一提的是：函數式語言里的樹是immutable的，修改特定節點生成新樹的原理是path copying，也就是從根節點到目標節點路徑上的節點都會被拷貝，而不是原地賦值修改，這是很多函數式數據結構上的操作O(log n)時間複雜度的來源。但是，我們還有一個叫做zipper的好東西！zipper是指向樹上某個節點的類似iterator一樣的東西。可以在O(1)的時間內實現：

  • 上下左右移動
  • 修改當前指向的節點
  • 取回以指向節點為根的子樹，或者從某個樹的根節點轉化而來

給定一個遞歸的樹定義，可以用很簡單的方法計算出它的zipper定義和各項操作的實現。這是一個非常實用的函數式語言里的樹結構相關的數據結構。

詳細的代碼和引用真的沒空貼了，又是好幾篇專欄的事。。等下周考完期中慢慢折騰。。

https://www.coursera.org/learn/progfun1/programming/Ogg05/object-oriented-sets

參見 Purely Functional Data Structure

咦, 好巧, 前幾個月做過一題樹結構的題, 代碼還在~

如圖, 我們要實現這樣一個樹結構, 每個節點有它自己的值. 我們需要達到這些功能:

  • - 修改當前節點的值;
  • - 往一個節點的左邊, 右邊添加節點;
  • - 為一個節點添加子節點;
  • - 訪問左, 右, 父, 子;
  • - 刪除當前節點以及它的孩子;

初看有些複雜, 但代碼很簡單. 首先, 我們採訪了根節點, 「請問根先森, 你姓胡嗎? 噢,不, 我是說, 您叫什麼名? 家裡幾個娃? 鄰居都有誰? 鄰居幾個娃? 祖宗都叫啥? 鄰居的祖宗….」, 然後我們就得到了這樣一張小卡片:

現在我們就可以開始實現需要的功能:修改當前值:

def replace({t, {l, [{_val, children}|r]}}, val), do:
{t, {l, [{val,children}|r]}}

添加左節點:

def insert_left({thread, {l, r}}, val), do:
{thread, {[{val, {[], []}}|l], r}}

添加右節點:

def insert_right({thread, {l, [h|t]}}, val), do:
{thread, {l, [h|[{val, {[], []}}|t]]}}

添加子節點:

def insert_child({t, {l, [{v, {left, right}}|r]}}, val), do:
{t, {l, [{v, {left, [{val, {[], []}}|right]}}|r]}}

訪問左, 右, 父, 子:

def left({thread, {[h|t], r}}), do:
{thread, {t, [h|r]}}

def right({thread, {l, [h|t]}}), do:
{thread, {[h|l], t}}

def children({thread, {l, [{val, children}|r]}}), do:
{[{l,[val|r]}|thread], children}

def parent({[{parentL, [val|parentR]}|thread], {l, r}}), do:
{thread, {parentL, [{val, {[], Enum.reverse(l)++r}}|parentR]}}

刪除節點:

def delete({thread, {l, [_|r]}}), do:
{thread, {l, r}} |&> parent

這裡的`|&>`是elixir的管道符, 表示將左邊的結果作為右邊函數的第一個參數來執行.

完成: )

ferd的一篇文章有專門講到這些 ferd.ca -&> Yet Another Article on Zippers, in Erlang

謝邀

可以看SICP:

Another way to implement scale-tree is to regard the tree as a sequence of sub-trees and use map. We map over the sequence, scaling each sub-tree in turn, and return the list of results. In the base case, where the tree is a leaf, we simply multiply by the factor:

(define (scale-tree tree factor)
(map (lambda (sub-tree)
(if (pair? sub-tree)
(scale-tree sub-tree factor)
(* sub-tree factor)))
tree))

Many tree operations can be implemented by similar combinations of sequence operations and recursion.

其實就是List of List

二叉樹在有代數數據類型(Algebraic data type)的語言可以這樣來表達 (Haskell)

data Tree a = Empty
| Branch a (Tree a) (Tree a)

換C裡面就是Tagged union

更加"廣泛"的樹可以叫Rose tree

data RoseTree a = RoseTree a [RoseTree a]

BTW, 函數式數據結構入門的可以看 ML程序設計教程 (豆瓣)

「樹」由節點組成，每個節點包含多個值，其中一個值是這個節點保存的值（value）。除了value，每個節點還需要0個到多個子樹。

有些函數式語言允許定義新的類型，為了表達「樹」這個結構，我們需要定義一個新的數據類型，tree。

函數式編程語言有一個數據結構叫list，即一連串同類型的數據（和array很像）。我們可以基於list來定義tree。

以二叉樹為例，即：（value，left，right）

(* 定義一個新類型，名為「tree」 *)
(* 該類型有兩個constructor：Br開頭的生成內部節點；Lf生成葉子節點。 *)
(* 內部節點的結構是（value，left，right） *)
(* 葉子節點表示null *)
(* 『a是這種樹的節點可以存儲的數據類型的佔位符 *)

type "a tree =
Br of "a * "a tree * "a tree
| Lf

函數式編程語言還有一個功能叫pattern matching，相當於高級的switch語句。我們可以用pattern matching和遞歸來處理tree的操作。

以輸出值為例，即：

(* 定義一個新函數來求一棵樹的非葉子節點的個數 *)
(* 「rec」表示這個函數存在遞歸 *)
(* 函數內部對參數tree進行pattern matching，根據tree類型的定義，傳入的參數要麼是內部節點，即Br （v，left，right）的形式；要麼是葉子節點。 *)
(* 如果是內部節點，那麼值為左右子樹非葉子節點個數的和加一（加上該節點） *)
(* 如果是葉子節點，那麼不計算，直接返回0 *)

let rec size tree =
match tree with
Br (v, left, right) -&> 1 + size left + size right
| Lf -&> 0

函數式語言自帶遞歸，處理遞歸定義的數據結構很方便。

謝邀，我google給您：

https://www.google.com/webhp?sourceid=chrome-instantion=1espv=2ie=UTF-8#q=erlang%20tree

https://www.google.com/webhp?sourceid=chrome-instantion=1espv=2ie=UTF-8#q=scala%20tree

https://www.google.com/webhp?sourceid=chrome-instantion=1espv=2ie=UTF-8#newwindow=1q=kotlin+tree

親請慢用哦。

只有葉子節點帶數據:

data Tree a = Leaf a | Node (Tree a) (Tree a)

都帶：

data Tree a = Leaf a | Node a (Tree a) (Tree a)

可以搜Recursive data type

謝邀~

&<感覺大家都好學術啊哈哈&>

樹的結構，我比較喜歡在實踐中定義 Node 結構，按需求對子節點進行引用，有點兒類似鏈表的感覺。就是類似下面的寫法吧，這個在 Leetcode 的題目中也好常見。

data class Node(val value: Int, var left: Node?, var right: Node?)

推薦閱讀：

※函數式編程所倡導使用的「不可變數據結構」如何保證性能？
※每一個 Haskell 中的「範疇論的」概念都可以去 co 嗎？
※Haskell的Lens是一個怎樣的庫？
※如何解釋 Lisp 中 call/cc 的概念？
※如何向一個只有命令式編程背景的人解釋函數式編程中的函數？

TAG:函數式編程 | 樹數據結構 |