ElixirですごいE本 5章

5章

すごいErlangゆかいに学ぼう！

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"

http://play.elixirbyexample.com/s/320b1787c4