understanding merge heap applying tree fold for heap sort
Please help me in understanding the below code. I understood how
map heapify
works with output
map heapify [34,25,28]
[Node 34 [],Node 25 [],Node 28 []]
Now how shall i understand this expression step by step.
merge_heaps = treefold merge_heap Nil
tried this by executing merge_heap individually.
merge_heap Nil . map heapify [34,25,28]
error
<interactive>:13:18: error:
* Couldn't match expected type `a > Heap a1'
with actual type `[Heap Integer]'
How the left folded tree structure is being interpreted to make max heap. struck. How shall i proceed further to make sense step by step.
How to map my understanding of heap sort in imperative languages something of sort from wikipedia in functional sense. How the unbalanced tree fold structure is being heap sorted.
 treefold (*) z [a,b,c,d,e,f] = (((a*b)*(c*d))*(e*f))
treefold f zero [] = zero
treefold f zero [x] = x
treefold f zero (a:b:l) = treefold f zero (f a b : pairfold l)
where
pairfold (x:y:rest) = f x y : pairfold rest
pairfold l = l  here l will have fewer than 2 elements
data Heap a = Nil  Node a [Heap a] deriving Show
heapify x = Node x []
heapsort :: Ord a => [a] > [a]
heapsort = flatten_heap . merge_heaps . map heapify
where
merge_heaps :: Ord a => [Heap a] > Heap a
merge_heaps = treefold merge_heap Nil
flatten_heap Nil = []
flatten_heap (Node x heaps) = x:flatten_heap (merge_heaps heaps)
merge_heap :: Ord a => []
merge_heap heap Nil = heap
merge_heap node_a@(Node a heaps_a) node_b@(Node b heaps_b)
 a < b = Node a (node_b: heaps_a)
 otherwise = Node b (node_a: heaps_b)
1 answer

The specific error you're encountering,
<interactive>:13:18: error: * Couldn't match expected type `a > Heap a1' with actual type `[Heap Integer]'
is because your test expression
merge_heap Nil . map heapify [34,25,28]
is an incorrect expansion of (part of) the defintion ofheapsort
by haskell's syntax.You want to apply the function
merge_heaps . map heapify
to[34,25,28]
. You can't do that by just concatenating the strings. In Haskell, function application by whitespace always has higher precedence than any binary operator.Your code is being parsed as
merge_heaps . (map heapify [34,25,28])
, which is a type error because the parenthesized subexpression isn't a function. You want something like(merge_heaps . map heapify) [34,25,28]
ormerge_heaps (map heapify [34,25,28])
or evenmerge_heaps . map heapify $ [34,25,28]
. Maybe not the last one for now. It can be confusing when you're still learning syntax and types.I think
merge_heaps (map heapify [34,25,28])
is easily the simplest  it removes all operators. Stick with that for the moment.
See also questions close to this topic

Haskell init list of n even/odd numbers
How can I init list of
n
odd
oreven
elements, can I do something like so?even_list :: Int > [Int] even_list n = [x  x < [1..], even x, length n]

Haskell custom parser terminology
So I'm doing a homework assignment to fill in implementation for a few functions that work with a custom Haskell parser (this only works with boolean logic). I'm trying to understand what the code means or is supposed to do on a high level. Some of this (marked with "(wrong?)") was implemented by me but I think most of it is wrong as I don't really understand what is going on.
What does it mean for Haskell to parse a con/disjunction ast? This should make something that looks like
p T_OR q
in parseOr right? How about parseNegation, parseNot, and parseParens?Sorry for the broad scope I just don't understand what these are supposed to be doing. This is all the relevant code so please give your best guess if you can't tell.
parseOr implements the single rule D > C  D. The definition says:  parse a conjunction AST and name it "p"  ensure that the next symbol in the stream is T_OR  parse a disjunction AST and name it "q"  return the AST "AND p q" > parseOr = do > p < parseConjunction > eat T_OR > q < parseDisjunction > return (OR p q) parseDisjunction implements the CFG rules for the D nonterminal: D > C  D D > C > parseDisjunction = parseOr <> parseConjunction parseAnd implements the rule C > N & C. > parseAnd = do > p < parseNegation > eat T_AND > q < parseConjunction > return (AND p q) parseConjunction should implement the rules for the C nonterminal: C > N & C C > N It will probably look almost identical to parseDisjunction, but with different parsers being combined. (wrong?) > parseConjunction = parseAnd <> parseDisjunction parseNot should implement the rule N > !N. (wrong?) > parseNot = do > p < parseNegation > eat T_NOT > return (NOT p) parseNegation should implement the rules for the N nonterminal: N > !N N > A (wrong?) > parseNegation = parseNot <> parseConjunction parseParens should implement the rule A > (D). (wrong?) > parseParens = do > eat L_PAREN > p < parseParens > eat R_PAREN > return (p)
eat implementation
eat :: Eq t => t > Parser t () eat x = Parser $ \ts > case ts of [] > Nothing (t:ts)  x == t > Just ((), ts)  otherwise > Nothing

How would you continue parsing after encountering an error with Happy in Haskell?
I am trying to write a parser with Happy for the Cool compiler language. I would like to have the parser continue its job even after it encounters a parsing error. Namely, if it encounters an error when parsing an expression in a block, I would like it to parse the next syntactically correct expression. However, I am having trouble implementing this.
Normally, when you encounter a parsing error, happy would call
parseError
and the computations automatically halt. I looked at several examples ofparseError
in the context of using Monads. However, the examples throwing an error would return anerror
value and the computation terminates automatically.I also tried using the error recovery methods described here, but my parser calls
parseError
and the parser stops automatically:https://www.haskell.org/happy/doc/html/secerror.html
Here is the grammar I use to parse expressions:
exprs :: { [Expression] } exprs : expr ';' { [$1] }  exprs expr ';' { $1 ++ [$2] }  error { [ExpressionError] } expr :: { Expression } expr : expr '+' expr { BinaryOp PlusTerminal $1 $3 }  expr '' expr { BinaryOp MinusTerminal $1 $3 }  expr '*' expr { BinaryOp TimesTerminal $1 $3 }  expr '/' expr { BinaryOp DivideTerminal $1 $3 }  int { IntegerExpr (T.getValue $1) }  objectID { IdentifierExpr (T.getName $1) }  '(' expr ')' { $2 }  '{' exprs '}' { BlockExpression $2 }
I was wondering how you guys were able to program Happy so it recovers from parsing errors.

Clojure Defining a variable inside of a function?
I have this variable, hand, that works just fine when I define it on its own.
(def yourHand (map ;;fn #(let [x %] (cond ;;hearts (< x 10) (* x 1) (< x 13) 10 ;;diamonds (< x 23) (* (mod x 13) 1) (< x 26) 10 ;;clubs (< x 36) (mod x 13) (< x 39) 10 ;;spades (< x 49) (mod x 13) (< x 52) 10 )) ;;list (take (randint 12) (repeatedly #(+ 1 (randint 52))))))
I would like to use this variable in this function here. This works just fine when I define the variable first then just use its name in the function.
(reduce + (vec (map #(let [x %] (cond (= x 1) 1 :else 0 )) yourHand)))
The issue arrises when I try to define the variable within the function, like this.
(reduce + (vec (map #(let [x %] (cond (= x 1) 1 :else 0 )) (def hand (map ;;fn #(let [x %] (cond ;;hearts (< x 10) (* x 1) (< x 13) 10 ;;diamonds (< x 23) (* (mod x 13) 1) (< x 26) 10 ;;clubs (< x 36) (mod x 13) (< x 39) 10 ;;spades (< x 49) (mod x 13) (< x 52) 10 )) ;;list (take (randint 12) (repeatedly #(+ 1 (randint 52)))))))))
This would not be necessary if not for 2 things. First, I would like to condense this program down to one function if possible (and I think it /is/ possible!). Second, I need to use this variable at another point in my program so I need to be able to reference it somehow.
Anyway, when I try to evaluate the above function, it complains that it doesn't know "how to create ISeq from: clojure.lang.Var". (This is the error: IllegalArgumentException Don't know how to create ISeq from: clojure.lang.Var clojure.lang.RT.seqFrom (RT.java:542)) I'm assuming this means that it doesn't know how to use my variable as a vector... but it seems to use it as a vector just fine when I define my variable outside of the function!
Any advice?

Java Comparator.comparing() with String charAt() Function
I am learning the new Comparator.comparing() function.
Here is the code I write to get a comparator for String to sort by the last char. To make the discussion simpler, here we just assume no null String and no index out of bound exception.
Comparator<String> comparator = Comparator.comparing(str > str.charAt(str.length()1));
The previous line works. I do get a comparator as I want.
But if I want to append a thenComparing(), the compiler start to fail.
Comparator<String> comparator = Comparator.comparing(str > str.charAt(str.length()1)).thenComparing(str2 > str2.charAt(str2.length()2)));
The error is: "cannot find symbol method length(), location: variable str of type java.lang.Object". Should be the same as the charAt() function.
Why without the thenComparing(), the compiler could detect that 'str' is a String, but after appending it, the compiler cannot detect 'str' as a String?

Numpy: Use one array as an iterative test for elements in another array
I have two arrays,
A
describes the start positions of 'blocks' of data,B
describes absolute positions of things of interest in the nonblocked, raw data.I want to be able to generate an index of the blockarray
A
that match the location of elements identified in blockB
.e.g.
import numpy as np A = np.array([0,10,13,25,27,33,100]) B = np.array([3, 3, 5, 21, 27, 32, 74])
I want to return an array that looks like:
array([0, 0, 0, 2, 4, 4, 5])
That is, the array that describes the indexposition, in terms of
A
, of the elements inB
.I could write a loop, something like:
list_holder = [] for e in B: list_holder.append(np.where(A>e)[0][0]1) np.array(list_holder)
But it turns out, for large arrays, this becomes rather slow  are there any functional or numpytricks that will perform this relatively simple operation as a oneliner?

Short circuit dispatching and stop condition in a stringliteral to type matcher
I am playing with some piece of code, taken from Avoid ifelse branching in string to type dispatching answer from Vittorio Romeo, but rewritten to use with C++14 cause Vittorios version uses C++17 fold expressions. I also thought the rewrite would be a good exercise.
Here is the code:
#include <type_traits> #include <iostream> #include <utility> #include <string> template<char... Cs> using ct_str = std::integer_sequence<char, Cs...>; template<typename T, T... Cs> constexpr ct_str<Cs...> operator""_cs() { return {}; } template<typename Name, typename T> struct named_type { using name = Name; using type = T; }; template<typename... Ts> struct named_type_list { }; using my_types = named_type_list< named_type<decltype("int"_cs), int>, named_type<decltype("bool"_cs), bool>, named_type<decltype("long"_cs), long>, named_type<decltype("float"_cs), float>, named_type<decltype("double"_cs), double>, named_type<decltype("string"_cs), std::string> >; template<std::size_t... Is, char... Cs> constexpr bool same_impl(const std::string& s, std::integer_sequence<char, Cs...>, std::index_sequence<Is...>) { const char c_arr[] = {Cs...}; for (std::size_t i = 0; i != sizeof...(Cs); ++i) { if (s[i] != c_arr[i]) return false; } return true; //Original C++17 (fold expression) //return ((s[Is] == Cs) && ...); } template<char... Cs> constexpr bool same(const std::string& s, std::integer_sequence<char, Cs...> seq) { std::cout << "checking '" << s << "' against '"; std::initializer_list<bool>{ bool(std::cout << Cs)... }; std::cout << "'\n"; return s.size() >= sizeof...(Cs) && same_impl(s, seq, std::make_index_sequence<sizeof...(Cs)>{}); } template<typename... Ts, typename F> void handle(named_type_list<Ts...>, const std::string& input, F&& f) { using expand_type = int[]; expand_type{ 0, (same(input, typename Ts::name{}) && (f(Ts{}), false), 0)... }; //(void)std::initializer_list<int> { // ( (same(input, typename Ts::name{}) && (f(Ts{}), false) ), 0)... //}; //Original C++17 (fold expression) //( (same(input, typename Ts::name{}) && (f(Ts{}), true) )  ...); } int main(int argc, char** argv) { const std::string input{"float"}; handle(my_types{}, input, [](auto t) { std::cout << typeid(typename decltype(t)::type).name() << "\n"; // TEST: define std::vector with value_type (matched type "float") and add a few values using mtype = typename decltype(t)::type; std::vector<mtype> x; x.push_back(2.2); // < does not compile }); return 0; }
I assume problem lies in the
handle
function that seems not to stop the evaluation properly. It should stop at the first invocation off()
in case of a match. Instead, it executes f() in case of a match as expected, but continues executing the remaining types in thenamed_type_list
.The current code results in this output:
checking 'float' against 'int' checking 'float' against 'bool' checking 'float' against 'long' checking 'float' against 'float' f checking 'float' against 'double' checking 'float' against 'string'
Actually I have no clue how to get that fixed. I tried to rewrite the C++17 fold expression using the
std::initializer_list
trick and also tried to use an expander (the uncommented part in thehandle
body. So I guess it is the expression itself not working properly.Unfortunately I am out of ideas whats really happening at this point, also the fact that I am not experienced with MetaProgramming/Compiletime evaluation.
Another problem arises with an possible use of this code: My use case would be in an XML property reader where I have type/value tags, e.g.
<attribute type="double" value="2.5"/>
, applying something like thehandle
function to get thetypename
from thetype
attribute value. That type I could use to further process the value.For this I added within the
handle
f()
body inmain()
3 lines, defining anstd::vector
with the found type and trying to add a value to it. This code does not compile, g++ responds witherror: no matching function for call to ‘std::vector<std::basic_string<char>, std::allocator<std::basic_string<char> > >::push_back(double)’
I guess this is the mixup out of compiletime and runtime behaviour and it does not work this way and that makes me curious how I could further process/use the matched type.
Thanks for your time on explanation, any help is greatly appreciated!

fold int option function
I wrote a program that takes integers of lists in lists and adds them together. Now I am trying to write this function again, but using int option integers instead.
I changed my original functions from
fun fold f base [] = base  fold f base (x::rest) = f x (fold f base rest); fun add x y = x+y; fun sumList L = fold add 0 L;
to
fun fold2 f base [] = SOME(base)  fold2 f base (x::rest) = f (SOME x) (fold2 f base rest); fun add2 x y = SOME (x + y); fun sumList2 L = fold2 add2 NONE L;
The add and fold2 functions both compile, but when I try to run variations of sumList2 I get operand don't agree errors.

Kotlin fold error "None of the following functions can be called with the arguments supplied"
I get an error for this fold function;
fun <T> addAll(num: List<T>) : T = num.fold(0, {x,y > x+y})
saying:
None of the following functions can be called with the arguments supplied.
However if I do:
fun addAll(num: List<Int>) : Int = num.fold(0, {x,y > x+y})
It works without problems. Is it possible to keep the function generic in order to use it for lists of both integers and doubles?

Finding complexity of heap function
I am going to use the following code for Heap sort (Link: https://github.com/kevinwayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/Heap.java)
Given the following code:
public static void sort(Comparable[] pq) { // Complexity: O(NLog N) int n = pq.length; // Complexity: O(1) for (int k = n/2; k >= 1; k) // Complexity: O(N) sink(pq, k, n); // Complexity: O(Log N) while (n > 1) { // Complexity: O(N) exch(pq, 1, n); // Complexity: O(1) sink(pq, 1, n); // Complexity: O(Log N) } } private static void sink(Comparable[] pq, int k, int n) { // Complexity: O(Log N) while (2*k <= n) { // Complexity: O(Log N) int j = 2*k; // Complexity: O(1) if (j < n && less(pq, j, j+1)) j++; // Complexity: O(1) if (!less(pq, k, j)) break; // Complexity: O(1) exch(pq, k, j); // Complexity: O(1) k = j; // Complexity: O(1) } } private static boolean less(Comparable[] pq, int i, int j) { // Complexity: O(1) return pq[i1].compareTo(pq[j1]) < 0; // Complexity: O(1) } private static void exch(Object[] pq, int i, int j) { // Complexity: O(1) Object swap = pq[i1]; // Complexity: O(1) pq[i1] = pq[j1]; // Complexity: O(1) pq[j1] = swap; // Complexity: O(1) }
I wanted to know if my thinking is correct?? I am a bit of a noob in this domain.

questions change value in heapsort
import java.util.ArrayList; import java.util.Collection; public class MaxHeap { private ArrayList<Student> students; public MaxHeap(int capacity) { students = new ArrayList<Student>(capacity); } public MaxHeap(Collection<Student> collection) { students = new ArrayList<Student>(collection); for(int i = size()/2; i >= 0; i) { maxHeapify(i); } } public Student getMax() { if(size() < 1) { throw new IndexOutOfBoundsException("No maximum value: the heap is empty."); } return students.get(0); } public Student extractMax() { Student value = getMax(); students.set(0,students.get(size()1)); students.remove(size()1); maxHeapify(0); return value; } public void changeKey(Student s, double newGPA) //need to change GPA of students
what's the method that I need to use to change the value of student ? For example, the first student has GPA 3.2, If i like to change the GPA to 3.8, how do I find a value in Students collection then change it?

questions Inserting in heapsort
import java.util.ArrayList; import java.util.Collection; public class MaxHeap { private ArrayList<Student> students; public MaxHeap(int capacity) { students = new ArrayList<Student>(capacity); } public MaxHeap(Collection<Student> collection) { students = new ArrayList<Student>(collection); for(int i = size()/2; i >= 0; i) { maxHeapify(i); } } public Student getMax() { if(size() < 1) { throw new IndexOutOfBoundsException("No maximum value: the heap is empty."); } return students.get(0); } public Student extractMax() { Student value = getMax(); students.set(0,students.get(size()1)); students.remove(size()1); maxHeapify(0); return value; } public void insert(Student elt) { private int lastOne; if (lastOne == students.length) throw new heapException("heap is full"); else { // I'm stuck here } }
As I understand, I Insert the element at last. Then compare it with its parent. If parent is greater than this latest insertion, return the element. Else swap parent and this child
private int parent(int index) { return (index  1)/2; } private int left(int index) { return 2 * index + 1; } private int right(int index) { return 2 * index + 2; } private int size() { return students.size(); } private void swap(int from, int to) { Student val = students.get(from); students.set(from, students.get(to)); students.set(to, val); } private void maxHeapify(int index) { int left = left(index); int right = right(index); int largest = index; if (left < size() && students.get(left).compareTo(students.get(largest)) > 0) { largest = left; } if (right < size() && students.get(right).compareTo(students.get(largest)) > 0) { largest = right; } if (largest != index) { swap(index, largest); maxHeapify(largest); } } }
Thank you everybody, now i can make a children and parent node, but How can add insert method ? I think about while or if statement. But cannot fingure out...