Last active
April 30, 2018 12:58
-
-
Save dcastro/3d09af9f72cd65996f1c0b839c813c36 to your computer and use it in GitHub Desktop.
Origami Programming Exercises
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Exercises: https://gist.github.com/hugoferreira/21f1f0ec23186adb5e6832e6aee618d6 | |
const eq = require('lodash').isEqual | |
const fold = (as, base) => (f) => { | |
let result = base | |
for (let i = 0; i < as.length; i++) | |
result = f(result, as[i]) | |
return result | |
} | |
const append = (x, xs) => xs.concat([x]) | |
const prepend = (x, xs) => [x].concat(xs) | |
const sum = (as) => fold(as, 0)((acc, x) => acc + x) | |
const foreach = (as) => (f) => fold(as, 0)((_, x) => f(x)) | |
const map = (as) => (f) => fold(as, [])((acc, x) => append(f(x), acc)); | |
const filter = (as) => (f) => fold(as, [])((acc, x) => f(x)? append(x, acc) : acc); | |
const filterNot = (as) => (f) => filter(as)(x => !f(x)) | |
const exists = (as) => (f) => fold(as, false)((acc, x) => acc || f(x)) | |
const forall = (as) => (f) => fold(as, true)((acc, x) => acc && f(x)) | |
const length = (as) => fold(as, 0)((acc, _) => acc + 1) | |
const isEmpty = (as) => fold(as, true)(_ => false) | |
const notEmpty = (as) => fold(as, false)(_ => true) | |
const reverse = (as) => fold(as, [])((acc, x) => prepend(x, acc)) | |
const first = (as) => fold(as, null)((acc, x) => acc === null? x : acc) | |
const last = (as) => fold(as, null)((_, x) => x) | |
const tail = (as) => fold(as, { index: 0, result: []})((state, x) => | |
!state.seenHead | |
? {seenHead: true, result: []} | |
: {seenHead: true, result: append(x, state.result)} | |
).result; | |
const second = (as) => fold(as, { index: 0, result: null })((state, x) => | |
state.index === 1 | |
? {index: state.index+1, result: x} | |
: {index: state.index+1, result: state.result} | |
).result; | |
const max = (as) => fold(as, null)((acc, x) => acc === null? x : x > acc? x : acc); | |
const maxBy = (as) => (f) => fold(as, null)((acc, x) => acc === null? x : f(x) > f(acc)? x : acc); | |
const min = (as) => fold(as, null)((acc, x) => acc === null? x : x < acc? x : acc); | |
const minBy = (as) => (f) => fold(as, null)((acc, x) => acc === null? x : f(x) < f(acc)? x : acc); | |
const find = (as) => (f) => fold(as, null)((acc, x) => f(x)? x : acc); | |
const takeWhile = (as) => (f) => fold(as, {taking: true, result: []})((state, x) => | |
state.taking && f(x) | |
? {taking: true, result: append(x, state.result)} | |
: {taking: false, result: state.result} | |
).result; | |
const dropWhile = (as) => (f) => fold(as, {dropping: true, result: []})((state, x) => | |
state.dropping && f(x) | |
? { dropping: true, result: state.result} | |
: { dropping: false, result: append(x, state.result)} | |
).result; | |
const partition = (as) => (f) => fold(as, [[], []])((acc, x) => | |
f(x) | |
? [append(x, acc[0]), acc[1]] | |
: [acc[0], append(x, acc[1])] | |
); | |
const splitAt = (as) => (i) => fold(as, {index: 0, result: [[], []]})((state, x) => | |
state.index < i | |
? {index: state.index+1, result: [append(x, state.result[0]), state.result[1]]} | |
: {index: state.index+1, result: [state.result[0], append(x, state.result[1])]} | |
).result; | |
const index = (as) => (i) => fold(as, {index: 0, result: null})((state, x) => | |
state.index === i | |
? {index: state.index+1, result: x} | |
: {index: state.index+1, result: state.result} | |
).result; | |
const zip = (as) => (bs) => fold(as, {index: 0, result: []})((state, a) => | |
state.index < bs.length | |
? {index: state.index+1, result: append([a, index(bs)(state.index)], state.result)} | |
: {index: state.index+1, result: state.result} | |
).result; | |
const zipWithIndex = (as) => fold(as, {index: 0, result: []})((state, x) => { | |
return {index: state.index+1, result: append([x, state.index], state.result)} | |
}).result; | |
const indexWhere = (as) => (f) => fold(as, {index: 0, result: null})((state, x) => | |
f(x) | |
? {index: state.index+1, result: state.index} | |
: {index: state.index+1, result: state.result} | |
).result; | |
const take = (as) => (i) => fold(as, [])((acc, x) => | |
acc.length < i | |
? append(x, acc) | |
: acc | |
); | |
const drop = (as) => (i) => fold(as, {index: 0, result: []})((state, x) => | |
state.index >= i | |
? { index: state.index+1, result: append(x, state.result)} | |
: { index: state.index+1, result: state.result} | |
).result; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{-# LANGUAGE LambdaCase #-} | |
module Origami where | |
import Prelude hiding (filter, map, head) | |
sum :: Num a => [a] -> a | |
sum = foldr (+) 0 | |
foreach :: Monad m => (a -> m ()) -> [a] -> m () | |
foreach f = foldr ((>>) . f) (pure ()) | |
map :: (a -> b) -> [a] -> [b] | |
map f = foldr ((:) . f) [] | |
filter :: (a -> Bool) -> [a] -> [a] | |
filter f = flip foldr [] $ \x acc -> | |
if f x | |
then x : acc | |
else acc | |
filterNot :: (a -> Bool) -> [a] -> [a] | |
filterNot f = filter (not . f) | |
exists :: (a -> Bool) -> [a] -> Bool | |
exists f = foldr (||) False. map f | |
forall :: (a -> Bool) -> [a] -> Bool | |
forall f = foldr (&&) True . map f | |
length :: Num b => [a] -> b | |
length = foldr (const (+1)) 0 | |
isEmpty :: [a] -> Bool | |
isEmpty = foldr (\_ _ -> False) True | |
notEmpty :: [a] -> Bool | |
notEmpty = foldr (\_ _ -> True) False | |
reverse :: [a] -> [a] | |
reverse = foldl (flip (:)) [] | |
first :: [a] -> Maybe a | |
first = foldl f Nothing | |
where | |
f Nothing x = Just x | |
f head _ = head | |
last :: [a] -> Maybe a | |
last = foldl (const Just) Nothing | |
tail :: [a] -> Maybe [a] | |
tail = foldl f Nothing | |
where | |
f Nothing _ = Just [] | |
f (Just xs) x = Just (xs ++ [x]) | |
second :: [a] -> Maybe a | |
second xs = foldl f Nothing $ zipWithIndex xs | |
where | |
f _ (x, 1) = Just x | |
f acc _ = acc | |
max :: Ord a => [a] -> Maybe a | |
max = maxBy id | |
maxBy :: Ord b => (a -> b) -> [a] -> Maybe a | |
maxBy f = foldl g Nothing | |
where | |
g Nothing x = Just x | |
g (Just x) y | |
| f x > f y = Just x | |
| otherwise = Just y | |
min :: Ord a => [a] -> Maybe a | |
min = minBy id | |
minBy :: Ord b => (a -> b) -> [a] -> Maybe a | |
minBy f = foldl g Nothing | |
where | |
g Nothing x = Just x | |
g (Just x) y | |
| f x < f y = Just x | |
| otherwise = Just y | |
find :: (a -> Bool) -> [a] -> Maybe a | |
find predicate = foldl g Nothing | |
where | |
g acc x = if predicate x then Just x else acc | |
takeWhile :: (a -> Bool) -> [a] -> [a] | |
takeWhile predicate = snd . foldl f (True, []) | |
where | |
f (taking, acc) x | |
| taking && predicate x = (True, acc ++ [x]) | |
| otherwise = (False, acc) | |
dropWhile :: (a -> Bool) -> [a] -> [a] | |
dropWhile predicate = snd . foldl f (True, []) | |
where | |
f (dropping, acc) x | |
| dropping && predicate x = (True, acc) | |
| otherwise = (False, acc ++ [x]) | |
partition :: (a -> Bool) -> [a] -> ([a], [a]) | |
partition f = foldr (\x (xs, ys) -> if f x then (x:xs, ys) else (xs, x:ys)) ([], []) | |
splitAt :: Int -> [a] -> ([a], [a]) | |
splitAt idx = foldr f ([], []) . zipWithIndex | |
where | |
f (x, i) (xs, ys) = if i < idx then (x:xs, ys) else (xs, x:ys) | |
index :: Int -> [a] -> Maybe a | |
index idx = foldl (\acc (x, i) -> if idx == i then Just x else acc) Nothing . zipWithIndex | |
zip :: [a] -> [b] -> [(a, b)] | |
zip = foldr f (const []) | |
where | |
f x functions = \case | |
[] -> [] | |
(y:ys) -> (x, y) : functions ys | |
zipWithIndex :: [a] -> [(a, Int)] | |
zipWithIndex = snd . foldl f (0, []) | |
where | |
f (idx, acc) x = (idx+1, acc ++ [(x, idx)]) | |
indexWhere :: (a -> Bool) -> [a] -> Maybe Int | |
indexWhere predicate = foldl f Nothing . zipWithIndex | |
where | |
f acc (x, i) = if predicate x then Just i else acc | |
take :: Int -> [a] -> [a] | |
take i = snd . foldl f (0, []) | |
where | |
f (count, acc) x | |
| count < i = (count + 1, acc ++ [x]) | |
| otherwise = (count, acc) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment