EveryOther.hs

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)

EveryOtherSpec.hs

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