23 lines
625 B
Haskell
23 lines
625 B
Haskell
{-# language DeriveFoldable #-}
|
|
|
|
import Data.Foldable (toList)
|
|
|
|
data BTree a b = Node a (BTree a b) (BTree a b)
|
|
| Val b
|
|
deriving Foldable
|
|
|
|
-- assuming list is sorted.
|
|
mkTree :: [a] -> BTree a [a]
|
|
mkTree [] = Val []
|
|
mkTree [x] = Node x (Val []) (Val [])
|
|
mkTree lst = Node x (mkTree l) (mkTree r)
|
|
where (l, x:r) = splitAt (length lst `div` 2) lst
|
|
|
|
binSplit :: Ord a => [a] -> [a] -> [[a]]
|
|
binSplit lims = toList . foldr add (mkTree lims)
|
|
where
|
|
add x (Val v) = Val (x:v)
|
|
add x (Node y l r) = if x < y
|
|
then Node y (add x l) r
|
|
else Node y l (add x r)
|