Anonymous user
Bin given limits: Difference between revisions
→{{header|Haskell}}: added binary search solution
m (→{{header|Haskell}}: added description) |
(→{{header|Haskell}}: added binary search solution) |
||
Line 759:
=={{header|Haskell}}==
Splitting the data into bins
Here tuple plays role of the Writer monad, so that sequential partitioning by each bin boundary
adds new bin contents.
Line 767:
binSplit :: Ord a => [a] -> [a] -> [[a]]
binSplit
where
(counts, rest) = foldM split ns
split l i = let (a, b) = partition (< i) l in ([a], b)
Line 780:
λ> binCounts [2,4,7] [1,4,2,6,3,8,9,4,1,2,7,4,1,5,1]
[4,3,5,3]</pre>
More efficient binning procedure exploits the binary search tree.
<lang 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
add :: Ord a => a -> BTree a [a] -> BTree a [a]
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)
binSplit :: Ord a => [a] -> [a] -> [[a]]
binSplit lims = toList . foldr add (mkTree lims)</lang>
Tasks examples
| |||