_.i      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefgh(c) Brett Wines 2014 BSD-stylebgwines@cs.stanford.edu experimentalportableNoneM KA typeclass for tree-like algebraic data types that are able to be graphed.aExpands a node into its show_node and children. For example, with the following example data type 7data Tree a = Empty | Leaf a | Node a (Tree a) (Tree a)*, you might have the following definition: expand (Empty) = Nothing expand (Leaf x) = Just (Just $ show x, []) expand (Node x l r) = Just (Just $ show x, [("L child", l), ("R child", r)])iReturns 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. (is_empty Empty = True is_empty _ = FalsejCGets the contents of a node as a string, if it exists. For example, show_node (Empty) = error "Empty nodes don't contain values." show_node (Leaf x) = Just x show_node (Node x _ _) = if x == 0 then Nothing else Just xkXGets the children of the current node together with edge label information. For example, get_children (Empty) = error "Empty nodes don't have children." get_children (Leaf _) = [] get_children (Node _ childrenMap) = map (show . fst) . toList $ childrenMaplNot exposed. Returns a String* to be put into a .dot file for the given  DAGGraphable: type. You shouldn't need to override this implementation. Returns a String to be put into a  =http://en.wikipedia.org/wiki/DOT_(graph_description_language)DOT file for the given  DAGGraphable type.8Graphs the given string as if it were the contents of a  =http://en.wikipedia.org/wiki/DOT_(graph_description_language)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.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. mijkl mijkl(c) Brett Wines 2014 BSD-stylebgwines@cs.stanford.edu experimentalportableNoneMAA typeclass for algebraic data types that are able to be graphed.?For these descriptions, assume the following example data type: 7data Tree a = Empty | Leaf a | Node a (Tree a) (Tree a)0Gets the value contained in a node. For example, cvalue (Empty) = error "Empty nodes don't contain values." value (Leaf x) = x value (Node x _ _) = x3Gets the children of the current node. For example, }get_children (Empty) = error "Empty nodes don't have children." get_children (Leaf _) = [] get_children (Node _ l r) = [l, r]Returns whether a node is empty. Sometimes, when declaring algebraic data types, it is desirable to have an "Empty" value constructor. If your data type does not have an "Empty" value constructor, just always return False. (is_empty Empty = True is_empty _ = Falsen Returns a String to be put into a .dot file for the given  Graphable: type. You shouldn't need to override this implementation.o Returns a String to be put into a .dot file for the given  Graphable6 type. You won't need to override this implementation. 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. pqno   pqno (c) Brett Wines 2014 BSD-stylebgwines@cs.stanford.edu experimentalportableNoneM? O(n)^ Partitions the given list into blocks of the specified length. Truncation behaves as follows: Epartition_with_block_size 3 [1..10] == [[1,2,3],[4,5,6],[7,8,9],[10]] 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]] O(B(n)), where B(n) is the n^th  (http://en.wikipedia.org/wiki/Bell_number Bell number9. Computes all partitions of the given list. For example, Zpowerpartition [1..3] == [[[1],[2],[3]], [[1,2],[3]], [[2],[1,3]], [[1],[2,3]], [[1,2,3]]]  O(n log(n))" Removes duplicate elements. Like  , but for r types, so it can be faster.s O(n log(n))M Removes duplicate elements according to the given comparator function. Like  , but for r types, so it can be faster.O(n)* Zips the list up into pairs. For example, Hpairify [1..6] == [(1,2), (3,4), (5,6)] pairify [1..5] == [(1,2), (3,4)]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]). O(n log(n))r Shuffles the given list. The second parameter is the seed for the random number generator that backs the shuffle.O(2^n)) Computes the powerset of the given list.O(n!)- Computes all permutations of the given list.O(2^k)1 Generates all subsets of the given list of size k.O(n^m)q 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 m2 is the size of the sets to generate. For example, msubsets_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]]O(n)3 Generates all cycles of a given list. For example, *cycles [1..3] == [[2,3,1],[3,1,2],[1,2,3]]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).sGiven 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). O(max(n, m))9 Merges the two given sorted lists of respective lengths n and m. A special case of " where the comparison function is t. O(max(n, m))9 Merges the two given sorted lists of respective lengths n and mQ, comparing elements in between the two lists with the given comparator function. O(min(n, m))0 Zips the two given lists of respective lengths n and m; as long as the pairs satisfy the given predicate function.O(n)= Removes an element at the specified index in the given list.O(n)B 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](O(n)) Identical to u[, but also contains the first element to satisfy the given predicate function. For example: *take_while_keep_last (<3) [1..] == [1,2,3](O(n))= Returns a pair where the first element is identical to what u7 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])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. 5(find_and_rest ((==) 3) [1..10]) == Just (3, [4..10]) (O(n^2))% Returns all contiguous subsequences.!(O(2^n))8 Returns all subsequences (contiguous and noncontiguous)"O(n)> Retuns all contiguous subsequences of the given length. E.g.: 0contiguous_subsequences_of_length 3 "1234567890" /"123","234","345","456","567","678","789","890"#O(n)* Returns whether the given list is sorted.$ O(n log(n)) Sorts the given list.%O(n)0 Returns whether the given list is a palindrome.& O(n log(n))D Returns whether the given list contains any element more than once.' O(nlog(n))O 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)]( O(nlog(n))O 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)])0Shorthand for applying the same parameter twice. f $$ x = f x x*#Shorthand for applicative functors: f <$*> l = f <$> l <*> l+ O(f log k)x, where k is the returnvalue, and f is the runtime of the input function on the lowest power of 2 above the returnvalue., O(f log k)x, where k is the returnvalue, and f is the runtime of the input function on the lowest power of 2 above the returnvalue.-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].O(n) Returns the noncontiguous sublist of elements greater than all previous elements, where "greater" is determined by the provided comparison function. For example: Qrunning_bests_by (Data.Ord.comparing length) [[1],[3,3,3],[2,2]] == [[1],[3,3,3]]/ O(min(n, m))E Interleaves elements from the two given lists of respective lengths n and m( in an alternating fashion. For example: 3interleave [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]0O(nf) Filters a list of length n^ leaving elemnts the indices of which satisfy the given predicate function, which has runtime f.1O(n)Q counts the number of elements in a list that satisfy a given predicate function.2O(n)T 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')]3Like v, but returns an integer.4Like w, but takes an integer.5Like x, but takes an integer.6List pre-pending.7List appending. snoc 4 [1,2,3] == [1,2,3,4]8O(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 )). The list must be finite and non-empty.9O(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 )). The list must be finite and non-empty.: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]];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]]<=Applies the given function to the first element of the tuple.=>Applies the given function to the second element of the tuple.>YApplies the given two functions to the respective first and second elements of the tuple.?IApplies the given function to the first and second elements of the tuple.@gApplies 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)ALike @!, but re-using the same function.BcApplies the given three functions to the respective first, second, and third elements of the tuple.C(Extracts the first element of a 3-tuple.D)Extracts the second element of a 3-tuple.E(Extracts the third element of a 3-tuple.FFApplies the given binary function to both elements of the given tuple.GLApplies the given ternary function to all three elements of the given tuple.A syz !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFG>  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFG> ! "#$%&+,'(-.*)/01289;:34567<=>?B@ACDEFGA syz !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFG(c) Brett Wines 2014 BSD-stylebgwines@cs.stanford.edu experimentalportableNoneM"HSA complete, monotonically increasing, infinite list of primes. Implementation from  >http://en.literateprograms.org/Sieve_of_Eratosthenes_(Haskell).IIA complete, monotonically increasing, infinite list of composite numbers.J O(log^3 n) Uses the  Hhttp://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#ExampleMiller-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.).).KO(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  4http://en.wikipedia.org/wiki/Prime-counting_function#the number of primes below a number2. Returns whether the parameter is a prime number.LO(min(n, m) (mod 10)), Returns whether the the two parameters are  $http://en.wikipedia.org/wiki/Coprimecoprime+, that is, whether they share any divisors.{O(1) phi(p^a) for prime p and nonnegative a.MO(k n log(n)^-1), where k" is the number of primes dividing n (double-counting for powers).NO(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  4http://en.wikipedia.org/wiki/Prime-counting_function#the number of primes below a number.OO(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  4http://en.wikipedia.org/wiki/Prime-counting_function#the number of primes below a number.PO(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  4http://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.QO(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  4http://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.RO(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  4http://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.SO(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  4http://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.TA 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).U:An infinite list of integers with irrational square roots.VqAn infinite list of the terms of the continued fraction representation of the square root of the given parameter.WO(k) The  /http://en.wikipedia.org/wiki/Continued_fractioncontinued fraction5 representation of the square root of the parameter. k) is the length of the continued fraction.X8Determines whether the given integer is a square number.Y*Takes the square root of a perfect square.Z 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 [BMultiplies the second parameter by the third, mod the first. E.g.:  mul_mod 5 2 4 3\<Adds the second parameter by the third, mod the first. E.g.:  add_mod 5 3 4 2]CSubtracts the third parameter from the second, mod the first. E.g.: sub_mod 5 16 7 4^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 3Note that only elements coprime to the modulus will have inverses; in cases that do not match this criterion, we return Nothing._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.`O(log m)K 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 11That is, 6 * 11 = 66, and 66 | 13 == 1 . Note that only elements coprime to the modulus will have inverses; in cases that do not match this criterion, we return Nothing.a*An infinite list of the Fibonacci numbers.bO(1)Q Area of a triangle, where the parameters are the edge lengths (Heron's formula).cO(1)Q Area of a triangle, where the parameters are the edge lengths (Heron's formula).dO(1) Calculates whether n is the e ^th power of any integer, where n is the first parameter and e is the second.e O(log_10(n)): Calculates the number of digits in an integer. Relies on logBase', so gives wrong answer for very large n.fReturns whether a Double# value is an integer. For example, 16.0 :: Double is an integer, but not 16.1.g Converts a Double to an Integer.h`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]2}~HIJKL{MNOPQRSTUVWXYZ[\]^_`abcdefgh!HIJKLMNOPQRSTUVWXYZ[\]^_`abcdefgh!HIKJLMONSRPQUTWVX\][^_Z`aYfdgebch2}~HIJKL{MNOPQRSTUVWXYZ[\]^_`abcdefgh      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstsutvwxyzwx{|}~|}|}|}| Zora-1.1.21Zora.Graphing.DAGGraphingZora.Graphing.TreeGraphing Zora.List Zora.Math Data.Listnub maximumBy minimumBy DAGGraphableexpand to_dotfilerender_dotfilerender TreeGraphablevalue get_childrenis_emptygraphpartition_with_block_sizepartition_into_kpowerpartition uniqueifypairify decyclifyshufflepowerset permutationssubsets_of_size subsets_of_size_with_replacementcycles has_cycles diff_infinitemergemerge_by zip_whileremove_at_indexsubseqtake_while_keep_lasttake_while_and_rest find_and_restcontiguous_subsequences subsequences!contiguous_subsequences_of_length is_sorted mergesort is_palindromecontains_duplicates elem_countselem_counts_by$$<$*>bsearchbsearch_1st_geq running_bestsrunning_bests_by interleavepassing_index_elemscountmap_keeplength'drop'take'conssnocmaximum_with_indexminimum_with_index minima_by maxima_bymap_fstmap_sndmap_pair map_pair_same zip_with_pairzip_with_pair_same map_triplefst3snd3trd3pair_op triple_opprimes compositesprime_miller_rabinprimecoprime euler_phifactor_number_is_perfect_squarefactor num_divisorsnum_divisors_of_n_squared_leq_n!divisors_number_is_perfect_squaredivisorssqrt_convergentsirrational_squares continued_fraction_sqrt_infinitecontinued_fraction_sqrtsquaresqrt_perfect_squarepow_modmul_modadd_modsub_moddiv_mod div_mod_primemultiplicative_inversefibstri_areatri_area_doubleis_power_of_int num_digitsis_int double_to_intsolve_linear_system show_nodeas_graphLabel as_dotfilezoldMapghc-prim GHC.ClassesOrd uniqueify_bycomparebaseGHC.List takeWhilelengthdroptakedecyclify_onceshuffle'euler_phi_for_powers_of_primesGHC.Realmod LinearSystem RowAndRHSrandom_integersprime_miller_rabin'factor'factors_to_divisorssqrt_convergents_recnext_continued_fraction_sqrtpow epsilon_round<+>scalesolve_row_echelon_systemsolve_row_echelon_system_rowperform_gaussian_elimination normalize