Origami Programming Exercises

origami-solution.js

// 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;

origami-solutions.hs

{-# 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)