Sha256: 8c39f0f084698ac4053f6cd277bde032bfd10183f405e0f681f46695b5c268b0
Contents?: true
Size: 1.14 KB
Versions: 396
Compression:
Stored size: 1.14 KB
Contents
module BST ( BST, bstLeft, bstRight, bstValue,
empty, singleton, insert, fromList, toList
) where
import Data.Foldable (foldl', toList)
data BST a = Tip
| Node (BST a) a (BST a)
deriving (Show, Eq)
-- This allows us to use the toList from Foldable.
-- This may be seen as gratuitous for just one toList function,
-- but keep in mind now this BST could use other Foldable functions too,
-- not just toList.
instance Foldable BST where
foldMap _f Tip = mempty
foldMap f (Node l v r) = foldMap f l `mappend` f v `mappend` foldMap f r
bstValue :: BST a -> Maybe a
bstValue Tip = Nothing
bstValue (Node _ v _) = Just v
bstLeft :: BST a -> Maybe (BST a)
bstLeft Tip = Nothing
bstLeft (Node l _ _) = Just l
bstRight :: BST a -> Maybe (BST a)
bstRight Tip = Nothing
bstRight (Node _ _ r) = Just r
empty :: BST a
empty = Tip
singleton :: a -> BST a
singleton x = Node empty x empty
insert :: Ord a => a -> BST a -> BST a
insert x Tip = singleton x
insert x (Node l v r) =
if v >= x
then Node (insert x l) v r
else Node l v (insert x r)
fromList :: Ord a => [a] -> BST a
fromList = foldl' (flip insert) empty
Version data entries
396 entries across 396 versions & 1 rubygems