Daily Haskell Exercise

[henix]

http://dailyhaskellexercise.tumblr.com/post/57051641046/even-odd-split

[henix]

evenOddSplit :: [a] -> ([a], [a])
evenOddSplit [] = ([], [])
evenOddSplit (x:xs) = case oddEvenSplit(xs) of (a,b) -> (x:a,b)

oddEvenSplit :: [a] -> ([a], [a])
oddEvenSplit [] = ([], [])
oddEvenSplit (x:xs) = case evenOddSplit(xs) of (a,b) -> (a,x:b)

main :: IO ()
main = print $ evenOddSplit [1,2,3,4,5,6,7]

[henix]

Scala's zipWithIndex:

def evenOddSplit[A](list: List[A]): (List[A], List[A]) = list.zipWithIndex.partition(t => t._2 % 2 == 0) match {
  case (es,os) => (es.map(e => e._1), os.map(o => o._1))
}

println(evenOddSplit(List(1, 2, 3, 4, 5, 6, 7)))

[henix]

2. Run-length encoding

http://dailyhaskellexercise.tumblr.com/post/57140686229/run-length-encoding

[henix]

My solution:

runLengthEncoding :: (Eq a) => [a] -> [(a,Int)]
runLengthEncoding [] = []
runLengthEncoding (x:xs) = case runLengthEncoding(xs) of
  [] -> [(x,1)]
  (y,n):ys -> if (x == y) then (y,n+1):ys else (x,1):(y,n):ys

eqSpan :: (Eq a) => [a] -> [[a]]
eqSpan [] = []
eqSpan (x:xs) = case span (== x) (x:xs) of (a,b) -> a:eqSpan(b)

rle :: (Eq a) => [a] -> [(a,Int)]
rle = map (\x -> (head x, length x)) . eqSpan

main :: IO()
main = do {
  print $ runLengthEncoding [0,0,1,0,0,1,1,1];
  print $ rle [0,0,1,0,0,1,1,1]
  }

后来才发现我重新发明了 Data.List.group

[henix]

Split a increasing list by break points

horizontalPath :: Ord a => [a] -> [a] -> [[a]]
horizontalPath _ [] = []
horizontalPath _ [_] = []
horizontalPath lst (x:y:xs) = case span (<= y) lst of
  (prefix, suffix) -> prefix:(horizontalPath (y:suffix) (y:xs))

main :: IO ()
main = print $ horizontalPath [0..4] [0,0,1,4]

[henix]

Test if a integer is a perfect power

Naive solution:

import Data.Numbers.Primes
import Data.List

import System.Environment

perfectPower :: Int -> Bool
perfectPower n = c > 1
  where c = (foldl gcd 0) . (map (\g -> length g)) . group . primeFactors $ n

main :: IO ()
main = do {
  args <- getArgs;
  let
    n = read $ head args :: Int
  in
   print $ perfectPower n
  }

[henix]

(map (\g -> length g)) can be simplified to (map length)

[henix]

最终版：

import Data.Numbers.Primes
import Data.List

import System.Environment

perfectPower :: Integral a => a -> Bool
perfectPower n = c > 1
  where c = (foldl gcd 0) . (map length) . group . primeFactors $ n

main :: IO ()
main = do {
  args <- getArgs;
  let
    n = read $ head args :: Integer
  in do {
    --print $ primeFactors n;
    print $ perfectPower n
    }
  }

枚举 m 的办法：

isPowerOf :: Integral int => int -> int -> Bool
isPowerOf 1 _ = True
isPowerOf n m = if r == 0 then isPowerOf q m else False
  where (q, r) = quotRem n m

perfectPower :: Integral int => int -> Bool
perfectPower n = any (\m -> isPowerOf n m) (takeWhile (\x -> x * x <= n) [2..n])

[henix]

枚举 k：

import Data.Maybe
import Data.Numbers.Primes

import System.Environment

-- test if there exists m such that n = m ^ k
-- O(log(n/k)logk) times multiply
testk :: Integer -> Integer -> Bool
testk n k = let
   findm l r
    | l > r = Nothing
    | n < v = findm l (mid-1)
    | n > v = findm (mid+1) r
    | otherwise = Just mid
    where
      mid = l + ((r - l) `div` 2)
      v = mid ^ k -- log k times multiply
  in
   isJust $ findm 2 ((n-1) `div` k + 1)

perfectPower :: Integer -> Bool
perfectPower n = any (testk n) (takeWhile (\x -> 2 ^ x <= n) primes)

main :: IO ()
main = do {
  args <- getArgs;
  let
    n = read $ head args :: Integer
  in do {
    print $ perfectPower n
    }
  }