↓ Ir para o conteúdo principal

← todas as notas

📎 Webclip

The beauty of recursion and pattern matching in functional programming languages

The post uses an Erlang lookup/2 function to show how recursion and pattern matching can make a binary-tree search concise and declarative. The function returns {ok, Val} when the key matches, undefined for an empty node, and otherwise recurses into Smaller or Larger depending on the key.

Reading notes
#

  • The function searches a binary tree for a passed Key and returns the associated Val or undefined.
  • Erlang allows multiple cases for the same function by changing the pattern in the parameters.
  • The cases are checked from top to bottom, so more specific patterns should come first.
  • lookup(_, {node, 'nil'}) ignores the first argument and returns undefined for an empty node.
  • lookup(Key, {node, {Key, Val, _, _}}) matches when the key in the node is the same as the requested key and returns {ok, Val}.
  • lookup(Key, {node, {NodeKey, _, Smaller, _}}) when Key < NodeKey uses a guard to decide to continue the search in Smaller.
  • lookup(Key, {node, {_, _, _, Larger}}) handles the remaining case and continues the search in Larger.
  • The post presents this as a functional way to express what the algorithm does instead of spelling out every step.