Skip to content

Instantly share code, notes, and snippets.

View deque-blog's full-sized avatar

deque-blog

4 followers · 5 following
View GitHub Profile
@deque-blog
deque-blog / bstCount.hs
Created December 17, 2016 15:44
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
deque-blog / FizzBuzz.hs
Last active December 17, 2016 17:24
{-# 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
deque-blog / FizzBuzz_DataDriven.hs
Created December 17, 2016 15:49
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
deque-blog / merge_sort_with_fold.hs
Last active December 25, 2016 09:55
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
deque-blog / merge_monoid_with_fold.hs
Last active December 25, 2016 09:56
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
deque-blog / merge_monoid_with_fold2.hs
Created December 22, 2016 19:50
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
deque-blog / merge_sorted_list.hs
Created December 22, 2016 20:06
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
deque-blog / generic_binary_counter.cpp
Last active December 22, 2016 20:53
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
deque-blog / sorted_range_merger.cpp
Last active December 23, 2016 15:31
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
deque-blog / accumulate_iter.cpp
Created December 22, 2016 21:54
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;
};