Zora 1.1.10.2 → 1.1.10.4

raw patch · 4 files changed

+364/−102 lines, 4 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• Zora.cabal +1/−1
• Zora/Graphing/DAGGraphing.hs +2/−2
• Zora/List.hs +280/−80
• Zora/Math.hs +81/−19

@@ -1,5 +1,5 @@ Name:		   Zora-Version:	   1.1.10.2+Version:	   1.1.10.4 Synopsis:      Graphing library wrapper + assorted useful functions  Description:   A library of assorted useful functions for working with lists, doing mathematical operations and graphing custom data types. Category:      Unclassified

@@ -56,8 +56,8 @@ 	-- | Expands a node into its show_node and children. For example, 	--  	-- > expand (Empty) = Nothing-	-- > expand (Leaf x) = Just (x, [])-	-- > expand (Node x l r) = Just (x, [("L child", l), ("R child", r)])+	-- > expand (Leaf x) = Just (show x, [])+	-- > expand (Node x l r) = Just (show x, [("L child", l), ("R child", r)]) 	expand :: g -> Maybe (Maybe String, [(Maybe String, g)])  -- | Returns whether a node is empty. Sometimes, when declaring algebraic data types, it is desirable to have an \"Empty\" show_node constructor. If your data type does not have an \"Empty\" show_node constructor, just always return @False@.

@@ -1,10 +1,10 @@ {-# LANGUAGE ScopedTypeVariables #-}  -- |--- Module      : Zora.List+-- Module   : Zora.List -- Copyright   : (c) Brett Wines 2014 ----- License     : BSD-style+-- License   : BSD-style -- -- Maintainer  : bgwines@cs.stanford.edu -- Stability   : experimental@@ -15,8 +15,13 @@  module Zora.List (+-- * Partitioning+  partition_with_block_size+, partition_into_k+, powerpartition+ -- * List transformations-  uniqueify+, uniqueify , pairify , decyclify , shuffle@@ -25,14 +30,10 @@ , powerset , permutations , subsets_of_size+, subsets_of_size_with_replacement , cycles , has_cycles --- * Partitioning-, partition_with_block_size-, partition_into_k-, powerpartition- -- * Operations with two lists , diff_infinite , merge@@ -44,6 +45,7 @@ , subseq , take_while_keep_last , take_while_and_rest+, find_and_rest , subsequences , contiguous_subsequences @@ -56,14 +58,33 @@ , contains_duplicates  -- * Assorted functions+, bsearch+, bsearch_1st_geq+, elem_counts+, running_bests+, running_bests_by+, (<$*>)+, interleave+, count , map_keep , maximum_with_index , minimum_with_index+, minima_by , length' , drop' , take' , cons , snoc++-- * Tuples+, map_fst+, map_snd+, map_pair+, fst3+, snd3+, trd3+, pair_op+, triple_op ) where  import qualified Data.List as List@@ -72,10 +93,60 @@  import System.Random +import Control.Applicative+ import Data.Monoid import Data.Maybe  -- ---------------------------------------------------------------------+-- Partitioning++-- | /O(n)/ Partitions the given list into blocks of the specified length. Truncation behaves as follows:+-- +-- > partition_with_block_size 3 [1..10] == [[1,2,3],[4,5,6],[7,8,9],[10]]+partition_with_block_size :: Int -> [a] -> [[a]]+partition_with_block_size len l =+    if (length l) <= len+        then [l]+        else (take len l) : (partition_with_block_size len (drop len l))++-- | /O(n)/ Partitions the given list into /k/ blocks. Truncation behavior is best described by example:+-- +-- > partition_into_k  3 [1..9]  == [[1,2,3],[4,5,6],[7,8,9]]+-- > partition_into_k  3 [1..10] == [[1,2,3,4],[5,6,7,8],[9,10]]+-- > partition_into_k  3 [1..11] == [[1,2,3,4],[5,6,7,8],[9,10,11]]+-- > partition_into_k  3 [1..12] == [[1,2,3,4],[5,6,7,8],[9,10,11,12]]+-- > partition_into_k  3 [1..13] == [[1,2,3,4,5],[6,7,8,9,10],[11,12,13]]+partition_into_k :: Int -> [a] -> [[a]]+partition_into_k k arr = partition_with_block_size block_size arr+    where+        block_size :: Int+        block_size = if (((length arr) `mod` k) == 0)+            then (length arr) `div` k+            else (length arr) `div` k + 1++-- | /O(B(n))/, where /B(n)/ is the /n/^th <http://en.wikipedia.org/wiki/Bell_number Bell number>. Computes all partitions of the given list. For example,+-- +-- > powerpartition [1..3] == [[[1],[2],[3]], [[1,2],[3]], [[2],[1,3]], [[1],[2,3]], [[1,2,3]]]+powerpartition :: [a] -> [[[a]]]+powerpartition [] = []+powerpartition l@(x:xs) =+    if length l == 1+        then [[[x]]]+        else concatMap (get_next_partitions x) . powerpartition $ xs+        where+            get_next_partitions :: a -> [[a]] -> [[[a]]]+            get_next_partitions e l = ([e] : l) : (map f indices)+                where+                    f i = (a i) ++ (b i) ++ (c i)+                    +                    a i = ((take' i) l)+                    b i = [e : (l !! (fromInteger i))]+                    c i = (drop' (i+1) l)++                    indices = [0..((length' l) - 1)]++-- --------------------------------------------------------------------- -- List transformations  -- | /O(n log(n))/ Removes duplicate elements. Like `Data.List.nub`, but for `Ord` types, so it can be faster.@@ -91,6 +162,8 @@ pairify l = []  -- | /O(l m)/, where /l/ is the cycle length and /m/ is the index of the start of the cycle. If the list contains no cycles, then the runtime is /O(n)/.+--+-- NOTE: this function will only find cycles in a list can be the output of an iterated function -- that is, no element may be succeeded by two separate elements (e.g. [2,3,2,4]). decyclify :: (Eq a) => [a] -> [a] decyclify = fromJust . List.find (not . has_cycles) . iterate decyclify_once @@ -100,11 +173,11 @@         then l         else take' (lambda' + mu'') l     where-        i       = alg1 (tail l) (tail . tail $ l)-        i'      = fromJust i+        i    = alg1 (tail l) (tail . tail $ l)+        i'  = fromJust i -        mu      = if (i  == Nothing) then Nothing else alg2 l (drop' i' l)-        mu'     = fromInteger . fromJust $ mu+        mu  = if (i  == Nothing) then Nothing else alg2 l (drop' i' l)+        mu'  = fromInteger . fromJust $ mu         mu''    = fromJust mu          lambda  = if (mu == Nothing) then Nothing else alg3 (drop (mu' + 1) l) (l !! mu')@@ -183,7 +256,7 @@         powerset_rec [] so_far = [so_far]         powerset_rec src so_far = without ++ with             where without = powerset_rec (tail src) (so_far)-                  with    = powerset_rec (tail src) ((head src) : so_far)+                  with  = powerset_rec (tail src) ((head src) : so_far)  -- TODO: actually O(n!)? -- | /O(n!)/ Computes all permutations of the given list.@@ -213,16 +286,20 @@                 without = subsets_of_size_rec (tail src) so_far size                 with    = subsets_of_size_rec (tail src) ((head src) : so_far) (size-1) -{-subsets_of_size_with_replacement_rec :: Integer -> [a] -> [a] -> [[a]]-subsets_of_size_with_replacement_rec size src so_far =-    case size == 0 of-        True  -> [so_far]-        False -> concat [map (e:) rec | e <- src]-        where rec = subsets_of_size_with_replacement_rec (size - 1)+-- | /O(n^m)/ Computes all sets comprised of elements in the given list, where the elements may be used multiple times, where `n` is the size of the given list and `m` is the size of the sets to generate. For example,+--+--   > subsets_of_size_with_replacement 3 [1,2] == [[1,1,1],[2,1,1],[1,2,1],[2,2,1],[1,1,2],[2,1,2],[1,2,2],[2,2,2]] -subsets_of_size_with_replacement :: [a] -> Integer -> [[a]]-subsets_of_size_with_replacement l size =-    subsets_of_size_with_replacement_rec size l []-}+subsets_of_size_with_replacement :: Integer -> [a] -> [[a]]+subsets_of_size_with_replacement n src = subsets_of_size_with_replacement' n src []+    where+        subsets_of_size_with_replacement' :: forall a. Integer -> [a] -> [a] -> [[a]]+        subsets_of_size_with_replacement' 0 src so_far = [so_far]+        subsets_of_size_with_replacement' n src so_far+            = concatMap (subsets_of_size_with_replacement' (n-1) src) $ nexts+            where+                nexts :: [[a]]+                nexts = map (: so_far) src  -- | /O(n)/ Generates all cycles of a given list. For example, -- @@ -243,54 +320,6 @@ has_cycles l = (decyclify_once l) /= l  -- ------------------------------------------------------------------------ Partitioning---- | /O(n)/ Partitions the given list into blocks of the specified length. Truncation behaves as follows:--- --- > partition_with_block_size 3 [1..10] == [[1,2,3],[4,5,6],[7,8,9],[10]]-partition_with_block_size :: Int -> [a] -> [[a]]-partition_with_block_size len l =-    if (length l) <= len-        then [l]-        else (take len l) : (partition_with_block_size len (drop len l))---- | /O(n)/ Partitions the given list into /k/ blocks. Truncation behavior is best described by example:--- --- > partition_into_k  3 [1..9]  == [[1,2,3],[4,5,6],[7,8,9]]--- > partition_into_k  3 [1..10] == [[1,2,3,4],[5,6,7,8],[9,10]]--- > partition_into_k  3 [1..11] == [[1,2,3,4],[5,6,7,8],[9,10,11]]--- > partition_into_k  3 [1..12] == [[1,2,3,4],[5,6,7,8],[9,10,11,12]]--- > partition_into_k  3 [1..13] == [[1,2,3,4,5],[6,7,8,9,10],[11,12,13]]-partition_into_k :: Int -> [a] -> [[a]]-partition_into_k k arr = partition_with_block_size block_size arr-    where-        block_size :: Int-        block_size = if (((length arr) `mod` k) == 0)-            then (length arr) `div` k-            else (length arr) `div` k + 1---- | /O(B(n))/, where /B(n)/ is the /n/^th <http://en.wikipedia.org/wiki/Bell_number Bell number>. Computes all partitions of the given list. For example,--- --- > powerpartition [1..3] == [[[1],[2],[3]], [[1,2],[3]], [[2],[1,3]], [[1],[2,3]], [[1,2,3]]]-powerpartition :: [a] -> [[[a]]]-powerpartition [] = []-powerpartition l@(x:xs) =-    if length l == 1-        then [[[x]]]-        else concatMap (get_next_partitions x) . powerpartition $ xs-        where-            get_next_partitions :: a -> [[a]] -> [[[a]]]-            get_next_partitions e l = ([e] : l) : (map f indices)-                where-                    f i = (a i) ++ (b i) ++ (c i)-                    -                    a i = ((take' i) l)-                    b i = [e : (l !! (fromInteger i))]-                    c i = (drop' (i+1) l)--                    indices = [0..((length' l) - 1)]---- --------------------------------------------------------------------- -- Operations with two lists  -- | Given two infinite sorted lists, generates a list of elements in the first but not the second. Implementation from <http://en.literateprograms.org/Sieve_of_Eratosthenes_(Haskell)>.@@ -355,7 +384,7 @@  -- | /(O(n))/ Returns a pair where the first element is identical to what `takeWhile` returns and the second element is the rest of the list -- --- > take_while_keep_last (<3) [1..] == [1,2,3]+-- > take_while_and_rest (<3) [1..10] == ([1,2],[3,4,5,6,7,8,9,10]) take_while_and_rest :: (a -> Bool) -> [a] -> ([a], [a]) take_while_and_rest f [] = ([], []) take_while_and_rest f l@(x:xs) = if not . f $ x@@ -364,6 +393,15 @@     where         rec = take_while_and_rest f xs +-- | /O(n)/ Like @Data.List.Find@, but returns a Maybe 2-tuple, instead, where the second element of the pair is the elements in the list after the first element of the pair.+--+-- > (find_and_rest ((==) 3) [1..10]) == Just (3, [4..10])+find_and_rest :: (a -> Bool) -> [a] -> Maybe (a, [a])+find_and_rest _ [] = Nothing+find_and_rest f (x:xs) = if f x+    then Just (x, xs)+    else find_and_rest f xs+ -- | /(O(n^2))/ Returns all contiguous subsequences. contiguous_subsequences :: [a] -> [[a]] contiguous_subsequences = (:) [] . concatMap (tail . List.inits) . List.tails@@ -372,7 +410,6 @@ subsequences :: [a] -> [[a]] subsequences = map reverse . powerset - -- --------------------------------------------------------------------- -- Sorting @@ -387,18 +424,14 @@         then l         else merge (mergesort a) (mergesort b)         where-            (a, b) = splitAt (floor ((fromIntegral $ length l) / 2)) l+            (a, b) = splitAt (((fromIntegral $ length l) `div` 2)) l  -- --------------------------------------------------------------------- -- Predicates --- TODO: O(n log(n))--- | /O(n^2)/ Returns whether the given list is a palindrome.+-- | /O(n)/ Returns whether the given list is a palindrome. is_palindrome :: (Eq e) => [e] -> Bool-is_palindrome s =-    if length s <= 1-        then True-        else (head s == last s) && (is_palindrome $ tail . init $ s)+is_palindrome l = l == (reverse l)  -- TODO: do this more monadically? -- | /O(n log(n))/ Returns whether the given list contains any element more than once.@@ -418,6 +451,121 @@ -- --------------------------------------------------------------------- -- Assorted functions +-- | /O(nlog(n))/ Counts the number of time each element appears in the given list. For example:+--+--  > elem_counts [1,2,1,4] == [(1,2),(2,1),(4,1)]+elem_counts :: (Ord a) => [a] -> [(a, Integer)]+elem_counts+    = map (\l -> (head l, length' l))+    . List.group+    . List.sort++-- | Shorthand for applicative functors:+--+--  > f <$*> l = f <$> l <*> l+(<$*>) :: Applicative f => (a -> a -> b) -> f a -> f b+f <$*> l = f <$> l <*> l++-- | /O(f log k)/, where k is the returnvalue, and f is the runtime of the input function on the lowest power of 2 above the returnvalue.+bsearch :: (Integer -> Ordering) -> Maybe Integer+bsearch f = bsearch' f lb ub+    where+        lb :: Integer+        lb+            = last+            . takeWhile (\n -> (f n) == LT)+            . map (\e -> 2^e)+            $ [1..]++        ub :: Integer+        ub = lb * 2++        bsearch' :: (Integer -> Ordering) -> Integer -> Integer -> Maybe Integer+        bsearch' f lb ub+            | (lb - ub <= 10)+                = List.find ((==) EQ . f)+                $ [lb..ub]+            | otherwise =+                case f curr of+                    LT -> bsearch' f curr ub+                    EQ -> Just curr+                    GT -> bsearch' f lb curr+                where+                    curr :: Integer+                    curr = (lb + ub) `div` 2++-- | /O(f log k)/, where k is the returnvalue, and f is the runtime of the input function on the lowest power of 2 above the returnvalue.+bsearch_1st_geq :: (Integer -> Ordering) -> Maybe Integer+bsearch_1st_geq f = bsearch_1st_geq' f lb ub+    where+        lb :: Integer+        lb+            = last+            . takeWhile (\n -> (f n) == LT)+            . map (\e -> 2^e)+            $ [1..]++        ub :: Integer+        ub = lb * 2++        bsearch_1st_geq' :: (Integer -> Ordering) -> Integer -> Integer -> Maybe Integer+        bsearch_1st_geq' f lb ub+            | (lb - ub <= 10)+                = List.find (\x -> ((==) EQ . f $ x) || ((==) GT . f $ x))+                $ [lb..ub]+            | otherwise =+                case f curr of+                    LT -> bsearch_1st_geq' f curr ub+                    EQ -> bsearch_1st_geq' f lb curr+                    GT -> bsearch_1st_geq' f lb curr+                where+                    curr :: Integer+                    curr = (lb + ub) `div` 2++-- | /O(n)/ Returns the noncontiguous sublist of elements greater than all previous elements. For example:+--+--   > running_bests [1,3,2,4,6,5] == [1,3,4,6]+running_bests :: forall a. (Ord a) => [a] -> [a]+running_bests = running_bests_by compare++-- | /O(n)/ Returns the noncontiguous sublist of elements greater than all previous elements, where "greater" is determined by the provided comparison function. For example:+--+--   > running_bests_by (Data.Ord.comparing length) [[1],[3,3,3],[2,2]] == [[1],[3,3,3]]+running_bests_by :: forall a. (Ord a) => (a -> a -> Ordering) -> [a] -> [a]+running_bests_by cmp [] = []+running_bests_by cmp (x:xs) = (:) x $ running_bests_by' xs x+    where+        running_bests_by' :: (Ord a) => [a] -> a -> [a]+        running_bests_by' [] _ = []+        running_bests_by' (x:xs) best_so_far = +            case best_so_far `cmp` x of+                LT -> x : (running_bests_by' xs x)+                EQ -> x : (running_bests_by' xs x)+                GT ->      running_bests_by' xs best_so_far++-- | /O(min(n, m))/ Interleaves elements from the two given lists of respective lengths `n` and `m` in an alternating fashion. For example:+--+--  > interleave [1,3,5,7] [2,4,6,8] == [1,2,3,4,5,6,7,8]+--+--  > interleave [1,3,5,7] [2,4,6] == [1,2,3,4,5,6,7]+--+--  > interleave [1,3,5] [2,4,6,8] == [1,2,3,4,5,6,8]+interleave :: [a] -> [a] -> [a]+interleave [] bs = bs+interleave as [] = as+interleave (a:as) (b:bs) = a : b : (interleave as bs)++-- /O(nf)/ Filters a list of length `n` leaving elemnts the indices of which satisfy the given predicate function, which has runtime `f`.+passing_index_elems :: (Int -> Bool) -> [a] -> [a]+passing_index_elems f+    = map snd+    . filter (f . fst)+    . zip [0..]++-- | /O(n)/ counts the number of elements in a list that satisfy a given predicate function.+count :: (a -> Bool) -> [a] -> Integer+count f = toInteger . length . filter f+ -- | /O(n)/ Maps the given function over the list while keeping the original list. For example: --  -- > map_keep chr [97..100] == [(97,'a'),(98,'b'),(99,'c'),(100,'d')]@@ -440,7 +588,9 @@ cons :: a -> [a] -> [a] cons = (:) --- | List post-pending.+-- | List appending.+--+--   > snoc 4 [1,2,3] == [1,2,3,4] snoc :: a -> [a] -> [a] snoc e l = l ++ [e] @@ -453,3 +603,53 @@ minimum_with_index :: (Ord a) => [a] -> (a, Integer) minimum_with_index xs =     List.minimumBy (Ord.comparing fst) (zip xs [0..])++-- | /O(n)/ Finds all minima of the given list by the given comparator function. For example,+--   > minima_by (Data.Ord.comparing length) [[1,2], [1], [3,3,3], [2]]+--   [[1], [2]]+minima_by :: (a -> a -> Ordering) -> [a] -> [a]+minima_by cmp [] = []+minima_by cmp (x:xs) = minima_by' cmp xs [x]+    where+        minima_by' :: (a -> a -> Ordering) -> [a] -> [a] -> [a]+        minima_by' _ [] so_far = so_far+        minima_by' cmp (x:xs) so_far =+            case x `cmp` (head so_far) of+                LT -> minima_by' cmp xs [x]+                EQ -> minima_by' cmp xs (x : so_far)+                GT -> minima_by' cmp xs so_far++-- ---------------------------------------------------------------------+-- Tuples++-- | Applies the given function to the first element of the tuple.+map_fst :: (a -> c) -> (a, b) -> (c, b)+map_fst = flip map_pair $ id++-- | Applies the given function to the second element of the tuple.+map_snd :: (b -> c) -> (a, b) -> (a, c)+map_snd = map_pair id++-- | Applies the given two functions to the respective first and second elements of the tuple.+map_pair :: (a -> c) -> (b -> d) -> (a, b) -> (c, d)+map_pair f g (a, b) = (f a, g b)++-- | Extracts the first element of a 3-tuple.+fst3 :: (a, b, c) -> a+fst3 (a, _, _) = a++-- | Extracts the second element of a 3-tuple.+snd3 :: (a, b, c) -> b+snd3 (_, b, _) = b++-- | Extracts the third element of a 3-tuple.+trd3 :: (a, b, c) -> c+trd3 (_, _, c) = c++-- | Applies the given binary function to both elements of the given tuple.+pair_op :: (a -> b -> c) -> (a, b) -> c+pair_op op (a, b) = op a b++-- | Applies the given ternary function to all three elements of the given tuple.+triple_op :: (a -> b -> c -> d) -> (a, b, c) -> d+triple_op op (a, b, c) = op a b c

@@ -1,8 +1,8 @@ -- |--- Module      : Zora.Math+-- Module	  : Zora.Math -- Copyright   : (c) Brett Wines 2014 ----- License     : BSD-style+-- License	 : BSD-style -- -- Maintainer  : bgwines@cs.stanford.edu -- Stability   : experimental@@ -20,41 +20,47 @@ , euler_phi , factor , divisors+, num_divisors  -- * Square roots , irrational_squares , sqrt_convergents , continued_fraction_sqrt , continued_fraction_sqrt_infinite+, square  -- * Assorted functions+, fibs+, sqrt_perfect_square , is_int , is_power_of_int-, int_to_double+, double_to_int , num_digits , tri_area , tri_area_double ) where +import qualified Zora.List as ZList+ import qualified Data.List as List  import Data.Maybe -import Zora.List+import Control.Applicative  -- --------------------------------------------------------------------- -- Prime numbers and division  -- | A complete, monotonically increasing, infinite list of primes. Implementation from <http://en.literateprograms.org/Sieve_of_Eratosthenes_(Haskell)>. primes :: [Integer]-primes = [2, 3, 5] ++ (diff_infinite [7, 9 ..] composites)+primes = [2, 3, 5] ++ (ZList.diff_infinite [7, 9 ..] composites) --- | A complete, monotonically increa?ing, infinite list of composite numbers.+-- | A complete, monotonically increasing, infinite list of composite numbers. composites :: [Integer] composites = foldr1 f $ map g $ tail primes 	where 		f (x:xt) ys = x : (merge_infinite xt ys)-		g p		 = [ n * p | n <- [p, p + 2 ..]]+		g p = [ n * p | n <- [p, p + 2 ..]]  		merge_infinite :: (Ord a) => [a] -> [a] -> [a] 		merge_infinite xs@(x:xt) ys@(y:yt) = @@ -104,15 +110,57 @@ -- TODO: don't start over in `primes` -- | /O(k n log(n)^-1)/, where /k/ is the number of primes dividing /n/ (double-counting for powers). /n log(n)^-1/ is an approximation for <http://en.wikipedia.org/wiki/Prime-counting_function the number of primes below a number>. factor :: Integer -> [Integer]-factor 0 = []-factor 1 = []-factor n = p : factor (n `div` p)-	where p = fromJust . List.find (\p -> (n `mod` p) == 0) $ primes+factor = factor' primes +factor' :: [Integer] -> Integer -> [Integer]+factor' _ 0 = []+factor' _ 1 = []+factor' primes' n = (:) p $ factor' primes_rest (n `div` p)+	where+		p :: Integer+		primes_rest :: [Integer]+		(p, primes_rest)+			= fromJust+			. ZList.find_and_rest (\p -> (n `mod` p) == 0)+			$ primes++-- | /O(k n log(n)^-1)/, where /k/ is the number of primes dividing /n/ (double-counting for powers). /n log(n)^-1/ is an approximation for <http://en.wikipedia.org/wiki/Prime-counting_function the number of primes below a number>. Essentially, linear in the time it takes to factor the number.+num_divisors :: Integer -> Integer+num_divisors+	= pred+	. product+	. map (succ . snd) -- succ because p_i^0 is a valid choice+	. ZList.elem_counts+	. factor++-- TODO: provide better bound here -- | /O(4^(k n log(n)^-1))/, where /k/ is the number of primes dividing /n/ (double-counting for powers). divisors :: Integer -> [Integer]-divisors = init . uniqueify . map product . powerset . factor+divisors = factors_to_divisors . ZList.elem_counts . factor+	where+		factors_to_divisors :: [(Integer, Integer)] -> [Integer]+		factors_to_divisors+			= init+			. List.sort+			. map product+			. map (map (\(p, a) -> p^a))+			. factors_to_divisors_rec +		factors_to_divisors_rec :: [(Integer, Integer)] -> [[(Integer, Integer)]]+		factors_to_divisors_rec = map (filter ((/=) 0 . snd)) . factors_to_divisors_rec'++		factors_to_divisors_rec' :: [(Integer, Integer)] -> [[(Integer, Integer)]]+		factors_to_divisors_rec' [] = []+		factors_to_divisors_rec' ((p, a):[]) = [[(p, a')] | a' <- [0..a]]+		factors_to_divisors_rec' ((p, a):factors) =+			(:) <$> curr_pairs <*> recs+			where+				curr_pairs :: [(Integer, Integer)]+				curr_pairs = [(p, a') | a' <- [0..a]]++				recs :: [[(Integer, Integer)]]+				recs = factors_to_divisors_rec factors+ -- --------------------------------------------------------------------- -- Square roots @@ -164,14 +212,28 @@  -- | /O(k)/ The <http://en.wikipedia.org/wiki/Continued_fraction continued fraction> representation of the square root of the parameter. /k/ is the length of the continued fraction. continued_fraction_sqrt :: Integer -> [Integer]-continued_fraction_sqrt n =-	take_while_keep_last (/= (2 * a0)) . continued_fraction_sqrt_infinite $ n+continued_fraction_sqrt n+	= ZList.take_while_keep_last (/= (2 * a0))+	. continued_fraction_sqrt_infinite+	$ n 		where 			a0 = floor . sqrt . fromInteger $ n +-- | Determines whether the given integer is a square number.+square :: Integer -> Bool+square = is_int . sqrt . fromIntegral+ -- --------------------------------------------------------------------- -- Assorted functions +-- | An infinite list of the Fibonacci numbers.+fibs :: [Integer]+fibs = 1 : 1 : zipWith (+) fibs (tail fibs)++-- | Takes the square root of a perfect square.+sqrt_perfect_square :: Integer -> Integer+sqrt_perfect_square = toInteger . ceiling . sqrt . fromInteger+ -- | /O(1)/ Area of a triangle, where the parameters are the edge lengths (Heron's formula). tri_area :: Integer -> Integer -> Integer -> Double tri_area a b c = @@ -187,21 +249,21 @@ tri_area_double a b c =  	sqrt $ p * (p-a) * (p-b) * (p-c) 		where+			p :: Double 			p = (a + b + c) / 2 - -- | /O(1)/ Calculates whether /n/ is the /e/^th power of any integer, where /n/ is the first parameter and /e/ is the second. is_power_of_int :: Integer -> Integer -> Bool is_power_of_int n e = (round (fromIntegral n ** (1/(fromInteger e))))^e == n --- | /O(log_10(n))/ Calculates the number of digits in an integer.+-- | /O(log_10(n))/ Calculates the number of digits in an integer. Relies on @logBase@, so gives wrong answer for very large `n`. num_digits :: Integer -> Integer num_digits n = (1 + (floor $ logBase 10 (fromInteger n)))  -- | Returns whether a @Double@ value is an integer. For example, @16.0 :: Double@ is an integer, but not @16.1@. is_int :: Double -> Bool-is_int x = x == (fromInteger (round x))+is_int x = x == (fromInteger . round $ x)  -- | Converts a @Double@ to an @Integer@.-int_to_double :: Double -> Integer-int_to_double = (toInteger . round)+double_to_int :: Double -> Integer+double_to_int = (toInteger . round)