-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Graphing library wrapper + assorted useful functions
--
-- A library of assorted useful functions for working with lists, doing
-- mathematical operations and graphing custom data types.
@package Zora
@version 1.1.21
-- | A typeclass with default implementation for graphing trees with
-- Haskell GraphViz. It is intended to be extremely
-- straightforward to graph your data type; you only need to define one
-- simple function (example implementation below).
module Zora.Graphing.DAGGraphing
-- | A typeclass for tree-like algebraic data types that are able to be
-- graphed.
class DAGGraphable g
expand :: DAGGraphable g => g -> Maybe (Maybe String, [(Maybe String, g)])
-- | Graphs the given DAGGraphable data type to a PDF file. Output
-- is written to the specified file. This is a convenience function that
-- is the composition of render_dotfile and to_dotfile.
render :: (Eq g, Show g, DAGGraphable g) => String -> g -> IO ()
-- | Returns a String to be put into a DOT file for the
-- given DAGGraphable type.
to_dotfile :: (Eq g, Show g, DAGGraphable g) => g -> String
-- | Graphs the given string as if it were the contents of a DOT
-- file. Output is written to the specified file. The first parameter is
-- the outfile name, and the second is the contents of the dotfile.
render_dotfile :: String -> String -> IO ()
-- |
-- - DEPRECATED; use Zora.Graphing.DAGGraphing instead
-- A typeclass with default implementation for graphing trees with
-- Haskell GraphViz. It is intended to be extremely
-- straightforward to graph your data type; you only need to define three
-- very simple functions (example implementations below).
--
-- | Deprecated: Use Zora.Graphing.DAGGraphing instead
module Zora.Graphing.TreeGraphing
-- | A typeclass for algebraic data types that are able to be graphed.
--
-- For these descriptions, assume the following example data type:
--
--
-- data Tree a = Empty | Leaf a | Node a (Tree a) (Tree a)
--
class TreeGraphable g
value :: TreeGraphable g => g a -> a
get_children :: TreeGraphable g => g a -> [g a]
is_empty :: TreeGraphable g => g a -> Bool
-- | Graphs the given TreeGraphable data type. Creates and writes
-- to a file named "graph.png", overwriting any existing files with that
-- name. You won't need to override this implementation.
graph :: (Show a, Ord a, TreeGraphable g) => g a -> IO String
-- | Assorted functions on lists.
module Zora.List
-- | 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]]
-- | 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]]
-- | O(B(n)), where B(n) is the n^th 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]]]
-- | O(n log(n)) Removes duplicate elements. Like nub, but
-- for Ord types, so it can be faster.
uniqueify :: Ord a => [a] -> [a]
-- | O(n) Zips the list up into pairs. For example,
--
--
-- pairify [1..6] == [(1,2), (3,4), (5,6)]
-- pairify [1..5] == [(1,2), (3,4)]
--
pairify :: [a] -> [(a, a)]
-- | 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]
-- | O(n log(n)) Shuffles the given list. The second parameter is
-- the seed for the random number generator that backs the shuffle.
shuffle :: Eq a => [a] -> Integer -> [a]
-- | O(2^n) Computes the powerset of the given list.
powerset :: [a] -> [[a]]
-- | O(n!) Computes all permutations of the given list.
permutations :: [a] -> [[a]]
-- | O(2^k) Generates all subsets of the given list of size
-- k.
subsets_of_size :: [a] -> Integer -> [[a]]
-- | 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 :: Integer -> [a] -> [[a]]
-- | O(n) Generates all cycles of a given list. For example,
--
--
-- cycles [1..3] == [[2,3,1],[3,1,2],[1,2,3]]
--
cycles :: Eq a => [a] -> [[a]]
-- | 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).
has_cycles :: Eq a => [a] -> Bool
-- | 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).
diff_infinite :: Ord a => [a] -> [a] -> [a]
-- | O(max(n, m)) Merges the two given sorted lists of respective
-- lengths n and m. A special case of merge_by where
-- the comparison function is compare.
merge :: Ord a => [a] -> [a] -> [a]
-- | O(max(n, m)) Merges the two given sorted lists of respective
-- lengths n and m, comparing elements in between the two
-- lists with the given comparator function.
merge_by :: Ord a => (a -> a -> Ordering) -> [a] -> [a] -> [a]
-- | O(min(n, m)) Zips the two given lists of respective lengths
-- n and m as long as the pairs satisfy the given predicate
-- function.
zip_while :: (a -> b -> Bool) -> [a] -> [b] -> [(a, b)]
-- | O(n) Removes an element at the specified index in the given
-- list.
remove_at_index :: Integer -> [a] -> [a]
-- | O(n) Returns the subsequence of the given length at starting at
-- index i of length m. For example,
--
--
-- subseq 4 5 [1..20] == [5,6,7,8,9]
--
subseq :: Integer -> Integer -> [a] -> [a]
-- | (O(n)) Identical to takeWhile, but also contains the
-- first element to satisfy the given predicate function. For example:
--
--
-- take_while_keep_last (<3) [1..] == [1,2,3]
--
take_while_keep_last :: (a -> Bool) -> [a] -> [a]
-- | (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_and_rest (<3) [1..10] == ([1,2],[3,4,5,6,7,8,9,10])
--
take_while_and_rest :: (a -> Bool) -> [a] -> ([a], [a])
-- | 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])
-- | (O(2^n)) Returns all subsequences (contiguous and
-- noncontiguous)
subsequences :: [a] -> [[a]]
-- | (O(n^2)) Returns all contiguous subsequences.
contiguous_subsequences :: [a] -> [[a]]
-- | O(n) Retuns all contiguous subsequences of the given length.
-- E.g.:
--
--
-- contiguous_subsequences_of_length 3 "1234567890"
--
--
--
-- - "123","234","345","456","567","678","789","890"
--
contiguous_subsequences_of_length :: Show a => Integer -> [a] -> [[a]]
-- | O(n) Returns whether the given list is sorted.
is_sorted :: Ord a => [a] -> Bool
-- | O(n log(n)) Sorts the given list.
mergesort :: Ord a => [a] -> [a]
-- | O(n) Returns whether the given list is a palindrome.
is_palindrome :: Eq e => [e] -> Bool
-- | O(n log(n)) Returns whether the given list contains any element
-- more than once.
contains_duplicates :: Ord a => [a] -> Bool
-- | 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
-- | 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
-- | 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)]
-- | 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_by :: Ord b => (a -> b) -> [a] -> [(a, Integer)]
-- | 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 :: Ord a => [a] -> [a]
-- | 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 :: Ord a => (a -> a -> Ordering) -> [a] -> [a]
-- | Shorthand for applicative functors:
--
--
-- f <$*> l = f <$> l <*> l
--
(<$*>) :: Applicative f => (a -> a -> b) -> f a -> f b
-- | Shorthand for applying the same parameter twice.
--
--
-- f $$ x = f x x
--
($$) :: (a -> a -> b) -> a -> b
-- | 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]
-- | 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]
-- | O(n) counts the number of elements in a list that satisfy a
-- given predicate function.
count :: (a -> Bool) -> [a] -> Integer
-- | 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')]
--
map_keep :: (a -> b) -> [a] -> [(a, b)]
-- | O(n) Finds the maximum element of the given list and returns a
-- pair of it and the index at which it occurs (if the maximum element
-- occurs multiple times, behavior is identical to that of
-- maximumBy). The list must be finite and non-empty.
maximum_with_index :: Ord a => [a] -> (a, Integer)
-- | O(n) Finds the minimum element of the given list and returns a
-- pair of it and the index at which it occurs (if the minimum element
-- occurs multiple times, behavior is identical to that of
-- minimumBy). The list must be finite and non-empty.
minimum_with_index :: Ord a => [a] -> (a, Integer)
-- | O(n) Finds all maxima of the given list by the given comparator
-- function. For example, > maxima_by (Data.Ord.comparing length)
-- [[1,2], [1], [3,3], [2]] [[1,2], [3,3]]
maxima_by :: (a -> a -> Ordering) -> [a] -> [a]
-- | 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]
-- | Like length, but returns an integer.
length' :: [a] -> Integer
-- | Like drop, but takes an integer.
drop' :: Integer -> [a] -> [a]
-- | Like take, but takes an integer.
take' :: Integer -> [a] -> [a]
-- | List pre-pending.
cons :: a -> [a] -> [a]
-- | List appending.
--
--
-- snoc 4 [1,2,3] == [1,2,3,4]
--
snoc :: a -> [a] -> [a]
-- | Applies the given function to the first element of the tuple.
map_fst :: (a -> c) -> (a, b) -> (c, b)
-- | Applies the given function to the second element of the tuple.
map_snd :: (b -> c) -> (a, b) -> (a, c)
-- | 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)
-- | Applies the given function to the first and second elements of the
-- tuple.
map_pair_same :: (a -> b) -> (a, a) -> (b, b)
-- | Applies the given three functions to the respective first, second, and
-- third elements of the tuple.
map_triple :: (a -> d) -> (b -> e) -> (c -> f) -> (a, b, c) -> (d, e, f)
-- | Applies the given function to respectively the first and second
-- elements of the two tuple. For example,
--
--
-- zip_with_pair (*) (^) (2,3) (5,4) == (10,27)
--
zip_with_pair :: (a -> c -> e) -> (b -> d -> f) -> (a, b) -> (c, d) -> (e, f)
-- | Like zip_with_pair, but re-using the same function.
zip_with_pair_same :: (a -> b -> c) -> (a, a) -> (b, b) -> (c, c)
-- | Extracts the first element of a 3-tuple.
fst3 :: (a, b, c) -> a
-- | Extracts the second element of a 3-tuple.
snd3 :: (a, b, c) -> b
-- | Extracts the third element of a 3-tuple.
trd3 :: (a, b, c) -> c
-- | Applies the given binary function to both elements of the given tuple.
pair_op :: (a -> b -> c) -> (a, b) -> c
-- | Applies the given ternary function to all three elements of the given
-- tuple.
triple_op :: (a -> b -> c -> d) -> (a, b, c) -> d
-- | Assorted mathematical functions.
module Zora.Math
-- | A complete, monotonically increasing, infinite list of primes.
-- Implementation from
-- http://en.literateprograms.org/Sieve_of_Eratosthenes_(Haskell).
primes :: [Integer]
-- | A complete, monotonically increasing, infinite list of composite
-- numbers.
composites :: [Integer]
-- | 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 the number of primes below a number.
-- Returns whether the parameter is a prime number.
prime :: Integer -> Bool
-- | O(log^3 n) Uses the Miller-Rabin primality test to
-- determine primality. Always correctly identifies primes, but may
-- misidentify some composites as primes (for most practical input
-- values, this will not happen (~3 below 10^9? 0 below 10^7.).).
prime_miller_rabin :: Integer -> Bool
-- | O(min(n, m) (mod 10)) Returns whether the the two parameters
-- are coprime, that is, whether they share any divisors.
coprime :: Integral a => a -> a -> Bool
-- | O(k n log(n)^-1), where k is the number of primes
-- dividing n (double-counting for powers).
euler_phi :: Integer -> Integer
-- | 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 the number of primes below a number.
factor :: Integer -> [Integer]
-- | 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 the number of primes below a number.
factor_number_is_perfect_square :: Integer -> [Integer]
-- | 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 the number of primes below a number.
-- Essentially, linear in the time it takes to factor the number.
divisors :: Integer -> [Integer]
-- | 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 the number of primes below a number.
-- Essentially, linear in the time it takes to factor the number.
divisors_number_is_perfect_square :: Integer -> [Integer]
-- | 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 the number of primes below a number.
-- Essentially, linear in the time it takes to factor the number.
num_divisors :: Integer -> Integer
-- | 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 the number of primes below a number.
-- Essentially, linear in the time it takes to factor the number.
num_divisors_of_n_squared_leq_n :: Integer -> Integer
-- | An infinite list of integers with irrational square roots.
irrational_squares :: [Integer]
-- | A list of fractions monotonically increasingly accurately
-- approximating the square root of the parameter, where each fraction is
-- represented as a pair of (numerator, denominator) See
-- http://en.wikipedia.org/wiki/Convergent_(continued_fraction).
sqrt_convergents :: Integer -> [(Integer, Integer)]
-- | O(k) The continued fraction representation of the square
-- root of the parameter. k is the length of the continued
-- fraction.
continued_fraction_sqrt :: Integer -> [Integer]
-- | An infinite list of the terms of the continued fraction representation
-- of the square root of the given parameter.
continued_fraction_sqrt_infinite :: Integer -> [Integer]
-- | Determines whether the given integer is a square number.
square :: Integral a => a -> Bool
-- | Adds the second parameter by the third, mod the first. E.g.:
--
--
-- add_mod 5 3 4
--
--
--
-- 2
--
add_mod :: Integral a => a -> a -> a -> a
-- | Subtracts the third parameter from the second, mod the first. E.g.:
--
--
-- sub_mod 5 16 7
--
--
--
-- 4
--
sub_mod :: Integral a => a -> a -> a -> a
-- | Multiplies the second parameter by the third, mod the first. E.g.:
--
--
-- mul_mod 5 2 4
--
--
--
-- 3
--
mul_mod :: Integral a => a -> a -> a -> a
-- | Divides the second parameter by the third, mod the first. More
-- explicitly, it multiplies the second by the multiplicative inverse of
-- the third, mod the first. E.g.:
--
--
-- div_mod 5 16 7
--
--
--
-- Just 3
--
--
-- Note that only elements coprime to the modulus will have inverses; in
-- cases that do not match this criterion, we return Nothing.
div_mod :: Integral a => a -> a -> a -> Maybe a
-- | Like div_mod, but with the assurance that the modulus is
-- prime (i.e. denominator will have an inverse). Thus, the returnvalue
-- doesn't need to be wrapped in a Maybe.
div_mod_prime :: Integral a => a -> a -> a -> a
-- | O(log_2 e) Raises base b (2nd param) to exponent
-- e (3rd param) mod m (1st param). E.g.:
--
--
-- pow_mod 13 2 4
--
--
--
-- 3
--
pow_mod :: Integral a => a -> a -> a -> a
-- | O(log m) Computes the multiplicative inverse of the second
-- parameter, in the group Z_m, where m is the first
-- parameter. E.g.:
--
--
-- multiplicative_inverse 13 6
--
--
--
-- Just 11
--
--
-- That is, 6 * 11 = 66, and 66 mod 13 == 1 . Note that only
-- elements coprime to the modulus will have inverses; in cases that do
-- not match this criterion, we return Nothing.
multiplicative_inverse :: Integral a => a -> a -> Maybe a
-- | An infinite list of the Fibonacci numbers.
fibs :: [Integer]
-- | Takes the square root of a perfect square.
sqrt_perfect_square :: Integer -> Integer
-- | Returns whether a Double value is an integer. For example,
-- 16.0 :: Double is an integer, but not 16.1.
is_int :: Double -> Bool
-- | 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
-- | Converts a Double to an Integer.
double_to_int :: Double -> 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
-- | O(1) Area of a triangle, where the parameters are the edge
-- lengths (Heron's formula).
tri_area :: Integer -> Integer -> Integer -> Double
-- | O(1) Area of a triangle, where the parameters are the edge
-- lengths (Heron's formula).
tri_area_double :: Double -> Double -> Double -> Double
-- | Solves a given system of linear equations. Can be subject to rounding
-- errors. Here's an example:
--
--
-- solve_linear_system [[2, 3, 4],[6, -3, 9],[2, 0, 1]] [20, -6, 8]
--
--
--
-- [4.999999999999999,6.0,-2.0]
--
solve_linear_system :: [[Double]] -> [Double] -> [Double]