deque-blog

bstCount :: (Int -> Integer) -> Int -> Integer
bstCount rec n
  | n <= 1 = 1
  | otherwise = sum [rec i * rec (n-1-i) | i <- [0..n-1]]

deque-blog

{-# LANGUAGE OverloadedStrings #-}
import Data.Monoid((<>))
import qualified Data.Text.Lazy as T
import qualified Data.Text.Lazy.Builder as B


-- The API of the fizz buzz

type Rule = B.Builder -> Int -> B.Builder

deque-blog

fizzBuzz :: [(Int, String)] -> Int -> String
fizzBuzz rules i =
  let r = concatMap (\(n,s) -> if mod i n == 0 then s else "") rules
  in if r == "" then show i else r

deque-blog

foldMergeSort :: (Ord a) => [a] -> [a]
foldMergeSort =
  foldl1 (flip merge) . map snd . foldl addToCounter []
  where
    addToCounter counter x = propagate ((1::Int,[x]) : counter)
    propagate [] = []
    propagate [x] = [x]
    propagate counter@(x:y:xs) -- x arrived last => combine on right
      | fst x == fst y = propagate ((fst x + fst y, merge (snd y) (snd x)) : xs)
      | otherwise      = counter

deque-blog

foldMonoidTree :: (Monoid a) => [a] -> a
foldMonoidTree =
  foldl1 (flip (<>)) . map snd . foldl addToCounter []
  where
    addToCounter counter x = propagate ((1::Int,x) : counter)
    propagate [] = []
    propagate [x] = [x]
    propagate counter@(x:y:xs) -- x arrived last => combine on right
      | fst x == fst y = propagate ((fst x + fst y, snd y <> snd x) : xs)
      | otherwise      = counter

deque-blog

newtype SortedList a = SortedList { unSortedList :: [a] }

instance (Ord a) =>  Monoid (SortedList a) where
  mempty = SortedList []
  mappend (SortedList a) (SortedList b) = SortedList $ merge a b

foldMergeSort :: (Ord a) => [a] -> [a]
foldMergeSort = unSortedList . foldMonoidTree . map (\x -> SortedList [x])

deque-blog

merge :: (Ord a) => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge l@(x:xs) r@(y:ys)
  | y < x     = y : merge l ys -- Keeps it stable
  | otherwise = x : merge xs r

deque-blog

template<typename Iterator, typename Value, typename BinaryOp>
Value add_to_counter(Iterator first, Iterator last,
                     Value carry, Value const &zero,
                     BinaryOp op)
{
    assert(carry != zero);
    for (; first != last; ++first) {
        if (*first == zero) {
            *first = carry;
            return zero;

deque-blog

template<typename Iterator>
struct merger
{
    using Value = typename std::iterator_traits<Iterator>::value_type;
    using SortedRange = std::pair<Iterator, Iterator>;

    SortedRange operator()(SortedRange const &lhs, SortedRange const &rhs) const {
        assert(lhs.second == rhs.first);
        std::vector<Value> tmp(lhs.first, lhs.second); //Copy the left range
        std::merge(

deque-blog

template<typename Iterator, typename Value, typename Accumulator>
Value accumulate_iter(Iterator first, Iterator last,
                      Value val, Accumulator fct)
{
    for (; first != last; ++first)
        val = fct(val, first);
    return val;
};