Skip to content

Instantly share code, notes, and snippets.

@ChrisPenner
Created August 27, 2019 05:36
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ChrisPenner/3aaf7cae15d9369a405c471e68831f04 to your computer and use it in GitHub Desktop.
Save ChrisPenner/3aaf7cae15d9369a405c471e68831f04 to your computer and use it in GitHub Desktop.
Binary tree search using lenses
-- Define a simple binary tree
data BT a
= BT { _leftTree :: BT a
, _val :: a
, _rightTree :: BT a
}
| Leaf
deriving (Show, Eq, Functor, Foldable, Traversable)
-- Generate traversals for the (partial) fields
makeLenses ''BT
-- Branch into one traversal or the other based on a predicate
branchBy :: (a -> Bool) -> Traversal' a b -> Traversal' a b -> Traversal' a b
branchBy p ta tb f s =
if p s then ta f s
else tb f s
-- Look for an element in a binary tree
binSearch :: Int -> BT Int -> Bool
binSearch n = has (deepOf (branchBy (anyOf val (> n)) leftTree rightTree) (val . only n))
-- 4
-- / \
-- / \
-- 2 7
-- \ /
-- 3 6
tree :: BT Int
tree =
BT (BT Leaf 2 (BT Leaf 3 Leaf))
4
(BT (BT Leaf 6 Leaf) 7 Leaf)
>>> binSearch 2 tree
True
>>> binSearch 3 tree
True
>>> binSearch 6 tree
True
>>> binSearch 20 tree
False
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment