5章

- 作者: Fred Hebert
- 出版社/メーカー: オーム社
- 発売日: 2014/08/11
- メディア: Kindle版
- この商品を含むブログ (1件) を見る
5.1 再帰の動き
リストの長さ
リストの長さを求める
defmodule Recursion do def len([]), do: 0 def len([_|t]), do: 1 + len t end IO.puts Recursion.len [1,2,3,4]
http://play.elixirbyexample.com/s/f148dc1a06
末尾再帰の長さ
末尾再帰に変更
defmodule Recursion do def tail_len(l), do: tail_len(l,0) def tail_len([], acc), do: acc def tail_len([_|t], acc), do: tail_len(t, acc+1) end IO.puts Recursion.tail_len [1,2,3,4]
http://play.elixirbyexample.com/s/527134add9
5.2 さらに末尾関数
複製(duplicate)する関数
defmodule Recursion do def tail_duplicate(n, term), do: tail_duplicate(n, term, []) def tail_duplicate(0, _, list), do: list def tail_duplicate(n, term, list) when n > 0 do tail_duplicate n-1, term, [term|list] end end IO.puts Recursion.tail_duplicate 10, "a"
http://play.elixirbyexample.com/s/2170806477
逆順(reverse)関数
Enum
にreverse/1
があるので自作しなくてよい
defmodule Recursion do def tail_duplicate(n, term), do: tail_duplicate(n, term, []) def tail_duplicate(0, _, list), do: list def tail_duplicate(n, term, list) when n > 0 do tail_duplicate n-1, term, [term|list] end def tail_reverse(list), do: tail_reverse(list, []) def tail_reverse([], acc), do: acc def tail_reverse([h|t], acc), do: tail_reverse(t, [h|acc]) end IO.inspect Recursion.tail_duplicate 10, "a" IO.inspect Recursion.tail_reverse [1,2,3,4]
http://play.elixirbyexample.com/s/e40fb03791
sublist関数
defmodule Recursion do def tail_duplicate(n, term), do: tail_duplicate(n, term, []) def tail_duplicate(0, _, list), do: list def tail_duplicate(n, term, list) when n > 0 do tail_duplicate n-1, term, [term|list] end def tail_reverse(list), do: tail_reverse(list, []) def tail_reverse([], acc), do: acc def tail_reverse([h|t], acc), do: tail_reverse(t, [h|acc]) def tail_sublist(list, n), do: tail_reverse tail_sublist(list, n, []) def tail_sublist(_, 0, sublist), do: sublist def tail_sublist([], _, sublist), do: sublist def tail_sublist([h|t], n, sublist) when n > 0 do tail_sublist(t, n-1, [h|sublist]) end end IO.inspect Recursion.tail_duplicate 10, "a" IO.inspect Recursion.tail_reverse [1,2,3,4] IO.inspect Recursion.tail_sublist [1,2,3,4,5,6], 3
http://play.elixirbyexample.com/s/25ed7f3fd8
zip関数
defmodule Recursion do def tail_duplicate(n, term), do: tail_duplicate(n, term, []) def tail_duplicate(0, _, list), do: list def tail_duplicate(n, term, list) when n > 0 do tail_duplicate n-1, term, [term|list] end def tail_reverse(list), do: tail_reverse(list, []) def tail_reverse([], acc), do: acc def tail_reverse([h|t], acc), do: tail_reverse(t, [h|acc]) def tail_sublist(list, n), do: tail_reverse tail_sublist(list, n, []) def tail_sublist(_, 0, sublist), do: sublist def tail_sublist([], _, sublist), do: sublist def tail_sublist([h|t], n, sublist) when n > 0 do tail_sublist(t, n-1, [h|sublist]) end def lenient_zip(x, y), do: lenient_zip(x, y, []) def lenient_zip(_, [], list), do: list def lenient_zip([], _, list), do: list def lenient_zip([x|xs], [y|ys], list) do lenient_zip(xs, ys, list ++ [{x,y}]) end end IO.inspect Recursion.tail_duplicate 10, "a" IO.inspect Recursion.tail_reverse [1,2,3,4] IO.inspect Recursion.tail_sublist [1,2,3,4,5,6], 3 IO.inspect Recursion.lenient_zip ["a","b","c","d","e","f"], [1,2,3,4,5,6]
http://play.elixirbyexample.com/s/1ad3d7cacc
素早く、ソート!
defmodule Recursion do def quicksort([]), do: [] def quicksort([pivot|rest]) do {smaller, larger} = partition pivot, rest, [], [] quicksort(smaller) ++ [pivot] ++ quicksort(larger) end def partition(_,[],smaller,larger), do: {smaller, larger} def partition(pivot, [h|t], smaller, larger) do if h <= pivot do partition pivot, t, [h|smaller], larger else partition pivot, t, smaller, [h|larger] end end def lc_quicksort([]), do: [] def lc_quicksort([pivot|rest]) do lc_quicksort(for smaller <- rest, smaller <= pivot, do: smaller) ++ [pivot] ++ lc_quicksort(for larger <- rest, larger > pivot, do: larger) end end IO.inspect Recursion.quicksort [5,10,2,3,4,8,1,11,20,25,30] IO.inspect Recursion.lc_quicksort [5,10,2,3,4,8,1,11,20,25,30]
http://play.elixirbyexample.com/s/d769f9ceff
5.3 リストを超えて
defmodule Tree do def empty, do: {:node, nil} def insert({:node, nil}, key, val) do {:node, {key, val, {:node, nil}, {:node, nil}}} end def insert({:node, {key, val, smaller, larger}}, new_key, new_val) when new_key < key do {:node, {key, val, insert(smaller, new_key, new_val), larger}} end def insert({:node, {key, val, smaller, larger}}, new_key, new_val) when new_key > key do {:node, {key, val, smaller, insert(larger, new_key, new_val)}} end def insert({:node, {key, _, smaller, larger}}, new_key, new_val) when new_key === key do {:node, {key, new_val, smaller, larger}} end def lookup({:node, nil}, _), do: :undefined def lookup({:node, {key, val, _, _}}, key), do: {:ok, val} def lookup({:node, {node_key, _, smaller, _}}, key) when key < node_key do lookup(smaller, key) end def lookup({:node, {node_key, _, _, larger}}, key) when key > node_key do lookup(larger, key) end end IO.inspect t1 = Tree.insert(Tree.empty(), "Jim Woodland", "jim.woodland@gmail.com") IO.inspect t2 = Tree.insert(t1, "Mark Anderson", "i.am.a@hotmail.com") addresses = Tree.insert(t2, "Anita Bath", "abath@someuni.edu") |> Tree.insert("Kevin Rovert", "myfairy@yahoo.com") |> Tree.insert("Wilson Longbrow", "longwil@gmail.com") IO.inspect addresses IO.inspect Tree.lookup addresses, "Anita Bath" IO.inspect Tree.lookup addresses, "Jacques Requin"