Skip to content

Instantly share code, notes, and snippets.

View deque-blog's full-sized avatar

deque-blog

3 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_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 / 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 / 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 / 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;
};
@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_merge_sort.cpp
Last active December 23, 2016 15:36
template<typename ForwardIterator>
void stable_sort_forward(ForwardIterator first, ForwardIterator last)
{
using Range = std::pair<ForwardIterator, ForwardIterator>;
using Counter = binary_counter<merger<ForwardIterator>, Range>;
Counter c { merger<ForwardIterator>{}, { last, last } };
accumulate_iter(first, last, &c,
[](auto c, auto it) {
c->add({it, std::next(it)});
@deque-blog
deque-blog / raw_loop_merge_sort.cpp
Created December 23, 2016 15:43
template<typename ForwardIterator>
void stable_sort_forward(ForwardIterator first, ForwardIterator last)
{
using Range = std::pair<ForwardIterator, ForwardIterator>;
using Counter = binary_counter<merger<ForwardIterator>, Range>;
Counter c { merger<ForwardIterator>{}, { last, last } };
for (; first != last; ++first) {
c.add(std::make_pair(first, std::next(first)));
}