📎 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
Keyand returns the associatedValorundefined. - 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 returnsundefinedfor 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 < NodeKeyuses a guard to decide to continue the search inSmaller.lookup(Key, {node, {_, _, _, Larger}})handles the remaining case and continues the search inLarger.- The post presents this as a functional way to express what the algorithm does instead of spelling out every step.
