{"id":5150,"date":"2017-01-26T21:14:15","date_gmt":"2017-01-26T21:14:15","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/higher-order-functions\/"},"modified":"2024-07-22T16:29:03","modified_gmt":"2024-07-22T16:29:03","slug":"higher-order-functions","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/higher-order-functions\/","title":{"rendered":"Higher-Order Functions"},"content":{"rendered":"

Higher-order functions are the pendant to First-Class Functions<\/a> because higher-order functions can take functions as an argument or return them as a result.<\/p>\n

<\/p>\n

Higher-order functions<\/h2>\n

\"\"<\/p>\n

The three classics: map, filter, and fold<\/h3>\n

Each programming language supporting programming in the functional style supports at least three functions map,<\/span> filter,<\/span> and fold.<\/span> map<\/span> applies a function to each element of its list. filter<\/span> removes all elements of a list not satisfying a condition. fold<\/span> is the most powerful of the three ones. fold<\/span> successively applies a binary operation to list pairs and reduces the list to a value.<\/p>\n

I can do better:<\/p>\n

\"MapFilterReduce\"<\/p>\n

The name variations<\/h4>\n

The statement that each programming language supporting programming in a functional style has to support the three functions map,<\/span> filter,<\/span> and reduce,<\/span> has few restrictions. The names of the three functions have variations in the different programming languages. You can see in the table the names of the Haskell functions in comparison with their names in C++ and Python.<\/p>\n

\"MapFilterFold\"<\/p>\n

I want to stress two points. Firstly, Haskell has four variations of the fold.<\/span> The variations are due to whether the binary operation starts at the beginning or at the end of the list and whether it has an initial value. Secondly, string concatenation of map and reduce (fold) gives MapReduce. This is no accident. The Google framework is based on a map and a reduce phase and is, therefore, based on the ideas of the functions map<\/span> and reduce<\/span> (fold).<\/span><\/p>\n

\"MapReduceEng\"<\/p>\n

The easiest way to understand the functions is to use them. As input, I choose a list (vec)<\/span> with the integers from 0 to 9 and a list (str)<\/span> with the words “Programming”,”in”,”a”,”functional”,”style.”<\/span> In the case of C++, the list is a std::vector.<\/span><\/p>\n

\n
\/\/ Haskell<\/span><\/strong>\nvec = [1..9]\nstr = [\"Programming\"<\/span>,\"in\"<\/span>,\"a\"<\/span>,\"functional\"<\/span>,\"style.\"<\/span>]\n\n\/\/ Python<\/span><\/strong>\nvec=range(1, 10)\nstr=[\"Programming\"<\/span>, \"in\"<\/span>, \"a\"<\/span>, \"functional\"<\/span>, \"style.\"<\/span>]\n\n\/\/ C++<\/span><\/strong>\nstd::vector<int<\/span>> vec{1, 2, 3, 4, 5, 6, 7, 8, 9}\nstd::vector<string> str{\"Programming\"<\/span>, \"in\"<\/span>, \"a\"<\/span>, \"functional\"<\/span>, \"style.\"<\/span>}\n<\/pre>\n<\/div>\n
For simplicity reasons, I will directly display the results in the list syntax of Haskell.<\/p>\n
map<\/h4>\n
map<\/span> applies a callable to each element of a list. A callable is all that behaves like a function. A callable can be, in C++, a function, a function object, or a lambda function. The best fit for higher-order functions is often a lambda function. That is for two reasons. On the one hand, you can concisely express your intent, and the code is easier to understand. On the other hand, the lambda function defines its functionality precisely where it is used. Because of that, the compiler gets maximum insight into the source code and has the maximum potential to optimize. That is the reason that you will often get more performant executables with a lambda function<\/p>\n
\n
\/\/ Haskell<\/span><\/strong>\nmap(\\a -> a * a) vec\nmap(\\a -> length a) str\n\n\/\/ Python<\/span><\/strong>\nmap(lambda x :x*x , vec)\nmap(lambda x : len(x), str)\n\n\/\/ C++<\/span><\/strong>\nstd::transform(vec.begin(), vec.end(), vec.begin(),\n              [](int<\/span> i){ return<\/span> i*i;} );\nstd::transform(str.begin(), str.end(), std::back_inserter(vec2),\n     [](std::string s){ return<\/span> s.length ();} );\n\n\/\/ [1,4,9,16,25,36,49,64,81]<\/span>\n<\/strong>\/\/ [11,2,1,10,6]<\/strong>\n<\/span>\n<\/pre>\n<\/div>\n
Of course, the syntax of lambda functions in Haskell, Python, and C++ is different. Therefore, a lambda function will be introduced in Haskell by a slash \\a \u2192 a*a<\/span>, but will be introduced in Python by the lambda: lambda x: x*x. <\/span>In C++, you have to use square brackets: [](int i){ return i*i; }<\/span>. These are only syntactical differences. More interesting is that you invoke functions in Haskell without braces and that Haskell and Python generate a list, while you can modify in C++ the existing std::vector<\/span> or fill a new one.<\/p>\n
filter<\/h4>\n
filter<\/span> keeps only these elements in the list that satisfy the predicate. A predicate is a callable that returns a boolean. Here is an example.<\/p>\n
\n
\/\/ Haskell<\/span><\/strong>\nfilter (\\x-> x <3 || x> 8) vec\nfilter (\\x -> isupper (head x)) sts\n\n\/\/ Python<\/span><\/strong>\nfilter(lambda x: x<3 or x>8 , vec)\nfilter(lambda x: x[0].isupper(), str)\n\n\/\/ C++<\/span><\/strong>\nauto<\/span> it = std::remove_if(vec.begin(), vec.end (),\n     [](int<\/span> i){return<\/span> ((i <3) or (i> 8))!});\nauto<\/span> it2 = std::remove_if(str.begin(),  str.end (), \n     [](std::string s) {return<\/span> !(std::isupper (s[0]));});\n\n\/\/ [1,2,9]<\/span>\n<\/strong>\/\/ [\"Programming\"]<\/strong>\n<\/span>\n<\/pre>\n<\/div>\n
The function composition isUpper(head x)<\/span> checks for each word if it starts (head x<\/span>) with a capital letter\u00a0 (isUpper<\/span>) ist.<\/p>\n
Two quick remarks to std::remove_if. std::remove_if<\/span> removes no element but returns the list’s new logical end. Afterward, you have to apply the erase-remove idiom<\/a>. The logic of std::remove_if<\/span> is the other way around. It will remove the elements satisfying the condition. Therefore, I have to negate the condition.<\/p>\n
fold<\/h4>\n
fold<\/span> is the most powerful of the three higher-order functions. You can implement map<\/span> and filter<\/span> by using fold.<\/span> The code snippet shows the calculation of the faculty of 9 and string concatenation in Haskell, Python, and C++.<\/p>\n
\n
\/\/ Haskell<\/span>\nfoldl (\\a b -> a * b) 1 vec\nfoldl (\\a b -> a ++ \":\"<\/span> ++ b ) \"\"<\/span> str\n\n\/\/Python<\/span><\/strong>\nreduce(lambda a , b: a * b, vec, 1)\nreduce(lambda a, b: a + \":\"<\/span> + b, str, \"\"<\/span>)\n\n\/\/ C++<\/span>\nstd::accumulate(vec.begin(), vec.end(), 1,\n                [](int<\/span> a, int<\/span> b){ return<\/span> a*b; });  \nstd::accumulate(str.begin(), str.end(), string(\"\"<\/span>),\n                [](std::string a,std::string b){ return<\/span> a+\":\"<\/span>+b; });\n\n\/\/ 362800 <\/span>\n\/\/ \":Programming:in:a:functional:style.\"\n<\/span><\/strong>\n<\/pre>\n<\/div>\n
foldl<\/span> needs as the Python pendant reduce<\/span> and the C++ pendant std::accumulate<\/span> an initial value. This is in the case of the faculty the 1; this is in the case of the string concatenation the empty string “”.\u00a0 Haskell requires two ++ symbols for adding two strings; Python and C++ only one.<\/p>\n
The strategy of std::accumulate<\/span> is a little bit difficult to get. Therefore, I have a graphic visualization of the processing.<\/p>\n
\"fold\"<\/p>\n
In the first iteration, the initial value 1 together with the first value of the input sequence is used as the arguments for the lambda function: 1*1= 1<\/span>. The result 1 is the first argument for the lambda function in the second iteration: 1*2= 2.<\/span> The third iteration has the previous result 2 as the first argument: 2*3= 6<\/span>. The last iteration returns the final result 24.<\/p>\n
What’s next?<\/h2>\n
Pure functional languages such as Haskell have the characteristic that their data is immutable. Therefore, Haskell can not have a for,<\/span> while,<\/span> or until<\/span> loop. In the next post<\/a>, I will write about the consequences of Haskell.<\/p>\n","protected":false},"excerpt":{"rendered":"
Higher-order functions are the pendant to First-Class Functions because higher-order functions can take functions as an argument or return them as a result.<\/p>\n","protected":false},"author":21,"featured_media":5145,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[365],"tags":[],"class_list":["post-5150","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-functional"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5150","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=5150"}],"version-history":[{"count":1,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5150\/revisions"}],"predecessor-version":[{"id":9771,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5150\/revisions\/9771"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/5145"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=5150"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=5150"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=5150"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}