Last active
June 29, 2016 03:39
-
-
Save corajr/f2836485f09e64b6f4cd04cc399c6978 to your computer and use it in GitHub Desktop.
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
module Data.Integer.EveryOther where | |
genericEveryOther :: Monoid a => [a] -> [a] | |
genericEveryOther [] = [] | |
genericEveryOther xs = zipWith mappend (scanl mappend mempty (init xs)) (scanr mappend mempty (tail xs)) | |
everyOther :: [Int] -> [Int] | |
everyOther [] = [] | |
everyOther xs = zipWith (*) (scanl (*) 1 (init xs)) (scanr (*) 1 (tail xs)) | |
everyOtherBrute :: [Int] -> [Int] | |
everyOtherBrute = map (product . snd) . selfAndRest | |
-- note that the `zipWith` section is the same as everyOther in structure | |
selfAndRest :: [a] -> [(a, [a])] | |
selfAndRest [] = [] | |
selfAndRest xs = zip xs (zipWith (++) (scanl (\xs' x -> xs' ++ [x]) [] (init xs)) (scanr (:) [] (tail xs))) | |
-- permutations can be defined in terms of `selfAndRest` like so | |
myPermutations :: [a] -> [[a]] | |
myPermutations [] = [[]] | |
myPermutations xs = concatMap f (selfAndRest xs) | |
where f (x, rs) = map (x:) (myPermutations rs) | |
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 ScopedTypeVariables #-} | |
module Data.Integer.EveryOtherSpec (main, spec) where | |
import Test.Hspec | |
import Test.QuickCheck | |
import Data.Integer.EveryOther | |
import Data.List (sort, permutations) | |
import Data.Monoid (Product(..)) | |
-- `main` is here so that this module can be run from GHCi on its own. It is | |
-- not needed for automatic spec discovery. | |
main :: IO () | |
main = hspec spec | |
spec :: Spec | |
spec = do | |
describe "selfAndRest" $ do | |
it "returns the empty list for an empty list" $ | |
selfAndRest ([] :: [Int]) `shouldBe` [] | |
it "returns the list [(a, [])] for a 1-element list" $ property $ | |
\(i :: Int) -> selfAndRest [i] === [(i, [])] | |
it "has the same elements as the original in the first position of the tuple" $ property $ | |
\(lst :: [Int]) -> map fst (selfAndRest lst) === lst | |
it "has lists that are all 1 element shorter in the second position of the tuple" $ property $ | |
\(lst :: [Int]) -> map (length . snd) (selfAndRest lst) === replicate (length lst) (length lst - 1) | |
it "returns correctly for a simple example" $ | |
selfAndRest "abcd" `shouldBe` [('a', "bcd"), ('b', "acd"), ('c', "abd"), ('d', "abc")] | |
describe "myPermutations" $ do | |
it "returns the same answers as library function" $ property $ | |
\(lst :: [Int]) -> length lst < 5 ==> sort (myPermutations lst) === sort (permutations lst) | |
describe "everyOther" $ do | |
it "returns the empty list for an empty list" $ | |
everyOther [] `shouldBe` [] | |
it "returns [1] for a 1-element list" $ property $ | |
\i -> everyOther [i] === [1] | |
it "returns the same as the brute force solution" $ property $ | |
\lst -> everyOther lst === everyOtherBrute lst | |
describe "genericEveryOther" $ do | |
it "returns the same as everyOther" $ property $ | |
\(lst :: [Int]) -> map getProduct (genericEveryOther (map Product lst)) === everyOther lst |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment