assignment operator haskell

Haskell for all

Sunday, july 16, 2017, demystifying haskell assignment.

This post clarifies the distinction between <- and = in Haskell, which sometimes mystifies newcomers to the language. For example, consider the following contrived code snippet:

The above program reads one line of input, and then prints that line twice with an exclamation mark at the end, like this:

Why does the first line use the <- symbol to assign a value to input while the second line uses the = symbol to define output ? Most languages use only one symbol to assign values (such as = or := ), so why does Haskell use two?

Haskell bucks the trend because the = symbol does not mean assignment and instead means something stronger than in most programming languages. Whenever you see an equality sign in a Haskell program that means that the two sides are truly equal. You can substitute either side of the equality for the other side and this substitution works in both directions.

For example, we define output to be equal (i.e. synonymous) with the expression input ++ "!" in our original program. This means that anywhere we see output in our program we can replace output with input ++ "!" instead, like this:

Vice versa, anywhere we see input ++ "!" in our program we can reverse the substitution and replace the expression with output instead, like this:

The language enforces that these sorts of substitutions do not change the behavior of our program (with caveats, but this is mostly true). All three of the above programs have the same behavior because we always replace one expression with another equal expression. In Haskell, the equality symbol denotes true mathematical equality.

Once we understand equality we can better understand why Haskell uses a separate symbol for assignment: <- . For example, lets revisit this assignment in our original program:

input and getLine are not equal in any sense of the word. They don't even have the same type!

The type of input is String :

... whereas the type of getLine is IO String :

... which you can think of as "a subroutine whose return value is a String ". We can't substitute either one for the other because we would get a type error. For example, if we substitute all occurrences of input with getLine we would get an invalid program which does not type check:

However, suppose we gloss over the type error and accept values of type IO String where the program expected just a String . Even then this substitution would still be wrong because our new program appears to request user input twice:

Contrast this with our original program, which only asks for a single line of input and reuses the line twice:

We cannot substitute the left-hand side of an assignment for the right-hand side of the assignment without changing the meaning of our program. This is why Haskell uses a separate symbol for assignment, because assignment does not denote equality.

Also, getLine and input are not even morally equal. getLine is a subroutine whose result may change every time, and to equate getLine with the result of any particular run doesn't make intuitive sense. That would be like calling the Unix ls command "a list of files".

Haskell has two separate symbols for <- and = because assignment and equality are not the same thing. Haskell just happens to be the first mainstream language that supports mathematical equality, which is why the language requires this symbolic distinction.

Language support for mathematical equality unlocks another useful language feature: equational reasoning . You can use more sophisticated equalities to formally reason about the behavior of larger programs, the same way you would reason about algebraic expressions in math.

Can we think of <- as andThen operator, applied in reverse?

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

What is the logic behind the use of different arrows (-> <-) in Haskell?

I've been thinking about language design lately, and reading over some of the new things in Haskell (always a nice source of inspiration). I'm struck by the many odd uses of the left <- and right -> arrow operators.

I guess the many different usages comes from prior art in math and other languages regarding arrow syntax, but is there some other reason not to try and make the usage more consistent or clear? Maybe I'm just not seeing the big picture?

The right arrow gets used as a type constructor for functions, the separator between argument and body of lambda expressions, separator for case statements, and it's used in pattern views, which have the form (e -> p) .

The left arrow gets used in do notation as something similar to variable binding, in list comprehensions for the same (I'm assuming they are the same, as list comprehensions look like condensed do blocks), and in pattern guards, which have the form (p <- e) .

Now the last examples for each arrow are just silly! I understand that guards and views serve different purposes, but they have almost identical form except that one is the mirror of the other! I've also always found it kind of odd that regular functions are defined with = but lambdas with -> . Why not use the arrow for both? Or the equals for both?

It also gets pretty odd when you consider that for comparing some calculated value against a constant, there's nearly a half-dozen ways to do it:

Variety is the spice of source code though, right?

• language-design

• 1 I think the <- in comprehensions is meant to resemble ∈ (meaning " element of ") not ← . –  detly Commented Aug 29, 2014 at 5:51
• 2 @detly I think it's because list comprehensions are meant to resemble do notation –  Benjamin Hodgson Commented Aug 29, 2014 at 10:38
• 1 @Carcigenicate: Actually, you can think of list comprehensions as just a different syntax for do-notation. In fact, they used to be "monad comprehensions" by default, and now you can still enable that functionality with an extension: Monad Comprehensions . –  Tikhon Jelvis Commented Nov 7, 2014 at 22:24
• 1 "Why not use the arrow for both? Or the equals for both?" The equality symbol makes sense for named function definitions because you're saying that applying the named function to its arguments is equivalent to the right hand side of the equation. Defining lambdas that way makes no sense notationally: x = x + 1 implies x is equal to its successor, which can't be true. –  Doval Commented Mar 11, 2015 at 12:07
• 2 The use of the arrow in list comprehension predates the "do" notation by over a decade. I'd guess the use of an arrow over a ∈ was probably because the former isn't really appropriate for lists and also so that generators don't look like guards. (See: D.A. Turner, 1981, "The semantic elegance of applicative languages.") The use of -> only came with Haskell; I don't think either KRC nor Miranda had lambdas. ML uses => for both lambda expressions and case expressions. The use of = comes from ML and KRC (which was first?) and fits well with equational reasoning about programs. –  Theodore Norvell Commented Apr 18, 2015 at 22:48

2 Answers 2

I've also always found it kind of odd that regular functions are defined with = but lambdas with ->. Why not use the arrow for both? Or the equals for both?

The equality symbol makes sense for named function definitions because it states that applying the named function to its arguments is equivalent to evaluating the right hand side of the equation. Defining lambdas that way makes no sense notationally: x = x + 1 implies x is equal to its successor, which can't be true.

The left arrow gets used in do notation as something similar to variable binding, in list comprehensions for the same (I'm assuming they are the same, as list comprehensions look like condensed do blocks), and in pattern guards, which have the form (p <- e).

All of those constructs bind a new variable. Using = here would not make much sense either, because a statement such as x = x + 1 implies that x refers to the same thing on both sides. A variable binding introduces a new x that's distinct from any x that may occur in the right hand side.

One alternative would've been to just use -> and place the variable on the right, but I believe placing it on the left is objectively more readable in cultures that read left to right. You scan text by moving your eyes along the left margin and thus placing all the variables on the left makes them easier to find. And although having two different symbols for variable bindings may not seem consistent, there's consistency in the position of the variable that gets bound; it's always on the left.

So that just leaves the question of why <- as opposed to some other symbol like := . I don't know, but I can guess. Look at what desugared monadic code looks like:

Considering that >>= with its arguments swapped is called =<< , it probably seemed natural to use a left-facing arrow.

The operator <- is used in two ways as described in Haskell operators :

• List comprehension generator;
• Single assignment operator in do-constr.

List comprehensions are syntactic sugar like the expression

import Data.Char (toUpper)

[toUpper c | c <- s]

where s :: String is a string such as "Hello". Strings in Haskell are lists of characters; the generator c <- s feeds each character of s in turn to the left-hand expression toUpper c , building a new list. The result of this list comprehension is "HELLO". (Of course, in this simple example you would just write map toUpper s .)

In the first versions of Haskell, the comprehension syntax was available for all monads. Later the comprehension syntax was restricted to lists. Since lists are an instance of monads, you can get list comprehension in terms of the do-notation.

Because of this, several Haskell programmers consider the list comprehension unnecessary now.

The example from above can be translated to list monad as follows:

do c <- s return (toUpper c)

For more info, see List comprehension .

• TBH, I first really deemed that @CodexArcanum asks about "logic behind" ->, <-. So, my answer actually is good for a school exam.Though, I hope it will be helpful for someone. –  Anton Danilov Commented Mar 11, 2015 at 15:30

Your Answer

Reminder: Answers generated by artificial intelligence tools are not allowed on Software Engineering Stack Exchange. Learn more

Sign up or log in

Post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged language-design haskell or ask your own question .

• The Overflow Blog
• Looking under the hood at the tech stack that powers multimodal AI
• Featured on Meta
• Join Stack Overflow’s CEO and me for the first Stack IRL Community Event in...
• User activation: Learnings and opportunities

Hot Network Questions

• Is it ethical to request partial reimbursement to present something from my previous position?
• Calm and Insight is the Normative Meditative Practice in Buddhism
• How to translate the letter Q to Japanese?
• Was the total glaciation of the world, a.k.a. snowball earth, due to Bok space clouds?
• Smallest prime q such that concatenation (p+q)"q is a prime
• Mark 6:54 - Who knew/recognized Jesus: the disciples or the crowds?
• Sync Layernotes between Projects
• What is all this —?
• 3D Chip Design using TikZ
• How to identify and uninstall packages installed as dependencies during custom backport creation
• How would you say "must" as in "Pet rabbits must be constantly looking for a way to escape."?
• Is it possible to monitor the current drawn by a computer from an outlet on the computer?
• Is "Canada's nation's capital" a mistake?
• Sent money to rent an apartment, landlord delaying refund with excuses. Is this a scam?
• Plotting Functions (Polynomials) with errors / Around values
• How to interpret odds ratio for variables that range from 0 to 1
• Are these slots in retaining wall bricks for rebars?
• string quartet + chamber orchestra + symphonic orchestra. Why?
• What can I do to limit damage to a ceiling below bathroom after faucet leak?
• meaning of a sentence from Agatha Christie (Murder of Roger Ackroyd)
• How to win a teaching award?
• Can you recommend a good book written about Newton's mathematical achievements?
• Big bang and the horizon problem
• Xcode 16.0 : unexpected service error: The Xcode build system has crashed

• Stack Overflow for Teams Where developers & technologists share private knowledge with coworkers
• Advertising & Talent Reach devs & technologists worldwide about your product, service or employer brand
• OverflowAI GenAI features for Teams
• OverflowAPI Train & fine-tune LLMs
• Labs The future of collective knowledge sharing
• About the company Visit the blog

Collectives™ on Stack Overflow

Find centralized, trusted content and collaborate around the technologies you use most.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Get early access and see previews of new features.

Difference between where bindings, let bindings and the single assignment operator (<-)

I do not understand the difference between the three syntaxes:

• where a = f (b)
• do a <- f (b)
• do let a = f (b)

I do understand somehow though that a <- f(b) is different from the other two, in most cases where I tried all three worked. Also I read somewhere on the net that per block you should try to get along with one let binding only in order to be "idiomatic". But I never seem to manage.

How do I decide what to use?

• do-notation

• 5 You must have tried wrong. I can think of almost no scenario where changing a <- f b to let a = f b (or vice versa) wouldn't break your code. That is assuming you're actually using a afterwards. –  sepp2k Commented Feb 13, 2012 at 0:32
• @sepp2k yes, but you can easily refactor your code to make it work. Same thing with let and where, "minor" refactoring is required. As I mentioned, I am aware that the single assignment operator is somehow different. Still I like to know what the difference is. –  J Fritsch Commented Feb 13, 2012 at 0:52
• 3 No, you can't. If f b has a non-monadic type a <- f b will simply not compile. There's no refactoring you can do to make it compile (unless you count stuffing a return in there to be refactoring...). If f b does have a monadic type, let a = f b will cause a to have the same type. This will almost certainly break the code using a . –  sepp2k Commented Feb 13, 2012 at 0:55
• @sepp2k Not sure if I can "compete" with you on this, but isn't it if I stay in the same monad it should not matter? –  J Fritsch Commented Feb 13, 2012 at 0:57
• 1 I'm not sure what you mean by that. If you have multiple <- s inside a do-block, their respective right operands must be in the same monad. But that has nothing to do with let . –  sepp2k Commented Feb 13, 2012 at 1:02

let foo = bar in ... simply defines foo to be the exact same thing as bar within the context of ... ; you could simply use textual substitution to replace all uses of foo in ... with (bar) and get the exact same result.

where clauses are similar to let...in expressions, but go at the end of a function clause, instead of being an expression. For instance,

There is no way to rewrite this with let...in without changing the guards into if...then...else s. Often, where clauses are used over let...in clauses purely for reasons of style.

The bind operator is something different entirely. It's used in do notation to "extract" a value from a monadic computation. That is, if foo has the type m a , then after x <- foo , x has the type a . All the other "binding" forms just define names, but <- is used for binding a computation's result to a name from within a monad. <- can only be used inside a do block, so it's exclusively used to build up a larger computation in the same monad as the action you're binding the result of.

let foo = bar in do notation is just a convenience; you can rewrite:

but that gets messy when you have a lot of such bindings, as the do blocks get nested deeper and deeper.

I don't know what the advice you mentioned is talking about; you can define multiple variables in a let...in block just fine, and

is more idiomatic than

Your Answer

Reminder: Answers generated by artificial intelligence tools are not allowed on Stack Overflow. Learn more

Sign up or log in

Post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged haskell syntax binding let do-notation or ask your own question .

• The Overflow Blog
• Looking under the hood at the tech stack that powers multimodal AI
• Featured on Meta
• Join Stack Overflow’s CEO and me for the first Stack IRL Community Event in...
• User activation: Learnings and opportunities
• What does a new user need in a homepage experience on Stack Overflow?
• Announcing the new Staging Ground Reviewer Stats Widget

Hot Network Questions

• What is the correct pipeline to process redirection logic
• How to avoid repeated input while using newcommand?
• How to interpret odds ratio for variables that range from 0 to 1
• Is "Canada's nation's capital" a mistake?
• How can I prove that this expression defines the area of the quadrilateral?
• In The Martian, what does Mitch mean when he is talking to Teddy and says that the space program is not bigger than one person?
• Are There U.S. Laws or Presidential Actions That Cannot Be Overturned by Successor Presidents?
• Wondering about ancient methods of estimating the relative planetary distances
• Big bang and the horizon problem
• What's the origin and first meanings of the term "grand piano"?
• How to assign a definition locally?
• Is it ethical to request partial reimbursement to present something from my previous position?
• A function to convert numbers from scientific notation to plain decimal
• Emergency belt repair
• Removing undermount sink
• Are these slots in retaining wall bricks for rebars?
• Why are no metals green or blue?
• Why did early pulps make use of “house names” where multiple authors wrote under the same pseudonym?
• Differences between “in average” and “on average”?
• PCB design references and roadmap
• Is it possible to make sand from bones ? Would it have the same properties as regular sand?
• Nonparametric test for means?
• Using a Compass to Detect Islands in the Sky
• Hungarian Immigration wrote a code on my passport

• Characters and Strings
• Type Signatures
• Records (Structs)
• Type Aliases
• Our Own Type Classes
• Deriving Instances Automatically
• Type Families
• More Functions for Functors
• Interlude: Monoids
• Non-Foldable Containers
• Either: Exception Handling with Error Information
• Reader: Computing with Context
• Writer: Producing a Log
• State: Stateful Computations
• Reader-Writer-State
• The MonadTrans Class
• Conclusions

Do Notation

Before we continue our exploration of monads, let's make working with them more convenient. The Maybe monad is great for (simple) exception handling, but it's not particularly convenient to work with. In Java, I can write things like:

This says that we assume that f cannot fail. Then we use g to produce b from a , which may fail, as can our application of h to x , a , and b , and our application of k to b and c . If something goes wrong, it must somehow have been caused by the values of x and a , so we pass x and a to our exception handler.

Here's what this would look like using our Maybe monad right now. Prepare for some ugliness:

Okay, I admit this is surprisingly compact, but it sure doesn't make it easy to see the logic. Let's take it apart to convince ourselves that it really matches the logic of the Java code. First our function types:

f cannot fail. Its type is

g , h , and k can fails, as can the exception handler. Their types are

Given the argument x , we call f x and assign the result to the local variable a . That's the same as int a = f(x) . Next we build the catch-try block. Let's add proper parentheses, which makes the code even uglier but reveals its structure better:

First we call g a . We could try to assign its result to another local variable b , but this wouldn't quite do what we want. This variable would have type Maybe Int because that's the return type of g a . In Java, g(a) produces an int ; the information that g(a) may fail is passed along behind the scenes in the form of exceptions. We want to do the same in Haskell, using our (>>=) operator of the Maybe monad to pass along the information that things may fail, and working with plain old Int s as long as things don't fail.

The way to do this is to build a function that expresses the computation that follows after the call g a . We want this function to have access to the return value of g a , so we bind the return value of g a to the argument of this function: g a >>= (\b -> ...) . Given the logic of (>>=) , this never calls (\b -> ...) if g a fails to produce a value. Just as in Java, the computation inside the try block aborts, and control transfers to the exception handler. If g a produces some value Just t , then (>>=) assigns t (without the Just !) to the argument b of (\b -> ...) and evaluates (\b -> ...) . Since b is the name of the function argument of (\b -> ...) , it is accessible everywhere inside (\b -> ...) , so it effectively acts like a local variable. That's exactly the same as in Java, where the code that comes after int b = g(a) has access to b , only the Haskell version is much uglier.

Let's continue. Our function (\b -> ...) should do exactly the same as the remainder of the try block in Java. So the next thing we should do is call h x a b . This may also fail, but if it doesn't, we want to assign the result to a variable c . We use the same trick again: we bind the return value to the argument of a function (\c -> ...) that represents whatever comes after h x a b . This successor function calls k b c , which is the return value of the whole computation if k b c succeeds.

We can think about the sequencing of steps in Java as nested scopes: int a = f(x) introduces the variable a . This variable is visible everywhere after this statement. int b = g(a) introduces the variable b . After this statement, both a and b are visible. int c = h(x, a, b) introduces the variable c . After this statement, a , b , and c are visible. And, of course, x is visible throughout the body of foo because it's foo 's argument. Our nesting of anonymous functions in Haskell achieves exactly the same effect.

If anything goes wrong in our pipeline g a >>= \b -> h x a b >>= \c -> k b c , then the result is Nothing , and catch invokes handler x a to recover from the exception, just as the Java code would jump to the catch block as soon as an exception is raised by one of the function calls.

Now let's make our Haskell code prettier. We can in fact implement foo like this:

Except for sprinkling in some do and let keywords, this looks remarkably like the Java code. Also note the use <- as the assignment operator instead of = . This will be important shortly.

So what does do do? It's a syntactic construct that allows us to pretend we're imperative programmers when we're "inside" a monad— any monad, not just Maybe .

Intuitively, you should read the sequence of statements inside a do -block as a sequence of steps to be executed in order, just as you would in an imperative program. So, here we say, let a be the result of f x . Then execute the code that comes after it, which mimics our try-catch block. This code has another do -block inside it, but that's fine: do -blocks can nest. The inner do-block starts by assigning g a to b , then h x a b to c , and finally evaluates k b c . Whatever k b c returns is the return value of the entire inner do -block because k b c is the last expression in this do -block. Note that there's no return statement. Indeed, as we have seen, return means something very different in a monad than in imperative languages.

If anything goes wrong inside the inner do -block, that is, if any of the functions g , h or k returns Nothing , then the value of the whole do -block is Nothing , so catch runs the exception handler.

Now here's the part that makes do -notation useful. Inside the do -block, the decoration of values provided by the monad is passed around completely behind the scenes, just as exceptions in Java are completely invisible to us as long as they don't happen. They're a hidden layer under the surface. So the assignment b <- g a assigns an Int to b , not a Maybe Int . The assignment operator <- inside a do -block peels off the decoration. The decoration is quietly passed along to the next statement. The manner in which this happens is determined by the (>>=) operator of the monad. We'll discuss this in the next section .

So what exactly are the rules for do -blocks? Here they are: Every do -block consists of a sequence of statements. Each of these statements can be of one of three forms, where we assume that the do -block expresses a computation in some monad m :

It can be a let -block that defines some local variables. These local variables are accessible anywhere inside the let -block and after it. Note that I said let - block not let - statement , because it is really a block. In our example above, we had let a = f x , but we can build let -blocks that assign more variables, as in

You can think about let -blocks as locally "turning off" the monad. The code inside the let -block is pure code, just as the variable definitions after let in a let ... in ... expression or in a where block. That's also why we use = for "assignments" inside a let -block. The <- assignment operator used in a do -block is reserved for peeling off the decoration from decorated values, and this works only outside of let -blocks.

It can be an assignment pat <- expr . In this case, expr must have the type m a for some type a , that is, it is an expression that evaluates to a value decorated using the monad m . <- peels off the decoration and assigns the value of type a to pat .

Note that I wrote pat , not var , to suggest that pat can be any pattern. It doesn't have to be a variable. For example, if we had an expression bar x y z of type m (Int, Bool, Double) , then we can write (i, _, d) <- bar x y z . Pattern matching then ignores the middle Bool component of the result of bar x y z , and it assigns the Int and Double components to i and d .

While we may use pattern matching in pat <- expr statements, this pattern matching must not fail. 1 If pat is a single variable, then pattern matching does not fail. If the function returns a tuple and we match its components to variables or wildcards, as we did in (i, _, d) <- bar x y z , this also cannot fail. When matching against data constructors of types with multiple data constructors or against specific values, those patterns can fail and should not be used.

Any variable bound as part of matching against the pattern pat is accessible anywhere after the statement pat <- expr .

It can be a single expression expr of some type m a . If this is the last expression in the do -block, then the value of this expression is the value of the whole do -block. If it isn't, then this expression is evaluated only for its side effect, and its return value is ignored. For example, we could have a function in the Maybe monad that fails if its argument is odd:

We can then write something like

Here, we call failIfOdd on x . If x is odd, this fails, returns Nothing , so the whole do -block fails and produces Nothing. Otherwise, we want to return x * y . Note that we do need to use return here, and I suspect this is also the reason why this method of the Monad class was named return . The reason is that the last expression of a do -block must have type m a , where m is our monad and a is the return type of the do -block. Here, we want the do -block to have type Maybe Int . The expression x * y has type Int . To turn it into a Maybe Int , we use return , because for the Maybe monad, return = Just .

There's one more important rule: The last statement in a do -block must always be an expression. It can't be a let -block or an assignment pat <- expr because the do -block must produce a value and the only statement that provides a value is a statement of the form expr . We're still programming functionally after all; do -notation only provides the illusion of imperative programming.

Another important point to make is that case and if then else are expressions in Haskell, and of course nothing prevents us from calling the function we're defining using do -notation recursively. Thus, we have the exact same control flow constructs available inside do as we have when writing pure functions. For example, here is a function that prints "Hello world!" several times, using the IO monad, which we will discuss shortly:

In this example, the whole do -block consists of a single if then else expression. Since greetRepeatedly should produce a value of type IO () , this is the value that both branches of the if then else expression need to produce. If reps == 0 , we return () . This doesn't really do anything. It simply wraps the provided value () in the IO monad, just as return () in the Maybe monad would produce the value Just () . If reps /= 0 , then the else -branch is itself a do -block that first prints "Hello world!" using putStrLn "Hello world!" and then calls greetRepeatedly recursively, with argument reps - 1 , that is, this recursive call takes care of the remaining reps - 1 times that "Hello world!" should be printed. The return value of this inner do -block is the value of its last statement, that is, the value produced by greetRepeatedly (reps - 1) . This obviously has the desired type IO () because that's what greetRepeatedly returns.

I used this example only to demonstrate that we can use standard control-flow constructs inside do -blocks. The seasoned Haskell programmer would use multiple equations to implement this function:

Even if a function decorates its return value using some monad and uses do -notation, it is still a normal function, and all the constructs we have discussed in the previous chapters can be used to define such a function.

There are some monads, such as Maybe , that are instances of the MonadFail class, a subclass of Monad . These are monads that can cope with failure or, in the case of Maybe , model the very essence of failure. A failed pattern match is such a failure. Thus, in monads that are instances of MonadFail , we can use patterns that may fail to match. In other monads, we can't.  ↩

CIS 194 : Home | Lectures & Assignments | Policies | Resources | Final Project

Haskell Basics

CIS 194 Week 1 14 January 2013

Suggested reading:

• Learn You a Haskell for Great Good, chapter 2
• Real World Haskell , chapters 1 and 2

What is Haskell?

Haskell is a lazy, functional programming language created in the late 1980’s by a committee of academics. There were a plethora of lazy functional languages around, everyone had their favorite, and it was hard to communicate ideas. So a bunch of people got together and designed a new language, taking some of the best ideas from existing languages (and a few new ideas of their own). Haskell was born.

So what is Haskell like? Haskell is:

There is no precise, accepted meaning for the term “functional”. But when we say that Haskell is a functional language, we usually have in mind two things:

Functions are first-class , that is, functions are values which can be used in exactly the same ways as any other sort of value.

The meaning of Haskell programs is centered around evaluating expressions rather than executing instructions .

Taken together, these result in an entirely different way of thinking about programming. Much of our time this semester will be spent exploring this way of thinking.

Haskell expressions are always referentially transparent , that is:

No mutation! Everything (variables, data structures…) is immutable .

Expressions never have “side effects” (like updating global variables or printing to the screen).

Calling the same function with the same arguments results in the same output every time.

This may sound crazy at this point. How is it even possible to get anything done without mutation or side effects? Well, it certainly requires a shift in thinking (if you’re used to an imperative or object-oriented paradigm). But once you’ve made the shift, there are a number of wonderful benefits:

Equational reasoning and refactoring : In Haskell one can always “replace equals by equals”, just like you learned in algebra class.

Parallelism : Evaluating expressions in parallel is easy when they are guaranteed not to affect one another.

Fewer headaches : Simply put, unrestricted effects and action-at-a-distance makes for programs that are hard to debug, maintain, and reason about.

In Haskell, expressions are not evaluated until their results are actually needed . This is a simple decision with far-reaching consequences, which we will explore throughout the semester. Some of the consequences include:

It is easy to define a new control structure just by defining a function.

It is possible to define and work with infinite data structures .

It enables a more compositional programming style (see wholemeal programming below).

One major downside, however, is that reasoning about time and space usage becomes much more complicated!

Statically typed

Every Haskell expression has a type, and types are all checked at compile-time . Programs with type errors will not even compile, much less run.

Throughout this course, we will focus on three main themes.

Static type systems can seem annoying. In fact, in languages like C++ and Java, they are annoying. But this isn’t because static type systems per se are annoying; it’s because C++ and Java’s type systems are insufficiently expressive! This semester we’ll take a close look at Haskell’s type system, which

Helps clarify thinking and express program structure

The first step in writing a Haskell program is usually to write down all the types . Because Haskell’s type system is so expressive, this is a non-trivial design step and is an immense help in clarifying one’s thinking about the program.

Serves as a form of documentation

Given an expressive type system, just looking at a function’s type tells you a lot about what the function might do and how it can be used, even before you have read a single word of written documentation.

Turns run-time errors into compile-time errors

It’s much better to be able to fix errors up front than to just test a lot and hope for the best. “If it compiles, it must be correct” is mostly facetious (it’s still quite possible to have errors in logic even in a type-correct program), but it happens in Haskell much more than in other languages.

Abstraction

“Don’t Repeat Yourself” is a mantra often heard in the world of programming. Also known as the “Abstraction Principle”, the idea is that nothing should be duplicated: every idea, algorithm, and piece of data should occur exactly once in your code. Taking similar pieces of code and factoring out their commonality is known as the process of abstraction .

Haskell is very good at abstraction: features like parametric polymorphism, higher-order functions, and type classes all aid in the fight against repetition. Our journey through Haskell this semester will in large part be a journey from the specific to the abstract.

Wholemeal programming

Another theme we will explore is wholemeal programming . A quote from Ralf Hinze:

“Functional languages excel at wholemeal programming, a term coined by Geraint Jones. Wholemeal programming means to think big: work with an entire list, rather than a sequence of elements; develop a solution space, rather than an individual solution; imagine a graph, rather than a single path. The wholemeal approach often offers new insights or provides new perspectives on a given problem. It is nicely complemented by the idea of projective programming: first solve a more general problem, then extract the interesting bits and pieces by transforming the general program into more specialised ones.”

For example, consider this pseudocode in a C/Java-ish sort of language:

This code suffers from what Richard Bird refers to as “indexitis”: it has to worry about the low-level details of iterating over an array by keeping track of a current index. It also mixes together what can more usefully be thought of as two separate operations: multiplying every item in a list by 3, and summing the results.

In Haskell, we can just write

This semester we’ll explore the shift in thinking represented by this way of programming, and examine how and why Haskell makes it possible.

Literate Haskell

This file is a “literate Haskell document”: only lines preceded by > and a space (see below) are code; everything else (like this paragraph) is a comment. Your programming assignments do not have to be literate Haskell, although they may be if you like. Literate Haskell documents have an extension of .lhs , whereas non-literate Haskell source files use .hs .

Declarations and variables

Here is some Haskell code:

The above code declares a variable x with type Int ( :: is pronounced “has type”) and declares the value of x to be 3 . Note that this will be the value of x forever (at least, in this particular program). The value of x cannot be changed later.

Try uncommenting the line below; it will generate an error saying something like Multiple declarations of `x' .

In Haskell, variables are not mutable boxes ; they are just names for values!

Put another way, = does not denote “assignment” like it does in many other languages. Instead, = denotes definition , like it does in mathematics. That is, x = 4 should not be read as “ x gets 4 ” or “assign 4 to x ”, but as “ x is defined to be 4 ”.

What do you think this code means?

Basic Types

Int s are guaranteed by the Haskell language standard to accommodate values at least up to \(\pm 2^{29}\), but the exact size depends on your architecture. For example, on my 64-bit machine the range is \(\pm 2^{63}\). You can find the range on your machine by evaluating the following:

(Note that idiomatic Haskell uses camelCase for identifier names. If you don’t like it, tough luck.)

The Integer type, on the other hand, is limited only by the amount of memory on your machine.

For floating-point numbers, there is Double :

There is also a single-precision floating point number type, Float .

Finally, there are booleans, characters, and strings:

GHCi is an interactive Haskell REPL (Read-Eval-Print-Loop) that comes with GHC. At the GHCi prompt, you can evaluate expressions, load Haskell files with :load ( :l ) (and reload them with :reload ( :r )), ask for the type of an expression with :type ( :t ), and many other things (try :? for a list of commands).

Try evaluating each of the following expressions in GHCi:

Note how `backticks` make a function name into an infix operator. Note also that negative numbers must often be surrounded by parentheses, to avoid having the negation sign parsed as subtraction. (Yes, this is ugly. I’m sorry.)

This, however, gives an error:

Addition is only between values of the same numeric type, and Haskell does not do implicit conversion. You must explicitly convert with:

fromIntegral : converts from any integral type ( Int or Integer ) to any other numeric type.

round , floor , ceiling : convert floating-point numbers to Int or Integer .

Now try this:

This is an error since / performs floating-point division only. For integer division we can use div .

If you are used to other languages which do implicit conversion of numeric types, this can all seem rather prudish and annoying at first. However, I promise you’ll get used to it—and in time you may even come to appreciate it. Implicit numeric conversion encourages sloppy thinking about numeric code.

Boolean logic

As you would expect, Boolean values can be combined with (&&) (logical and), (||) (logical or), and not . For example,

Things can be compared for equality with (==) and (/=) , or compared for order using (<) , (>) , (<=) , and (>=) .

Haskell also has if -expressions: if b then t else f is an expression which evaluates to t if the Boolean expression b evaluates to True , and f if b evaluates to False . Notice that if - expressions are very different than if - statements . For example, with an if-statement, the else part can be optional; an omitted else clause means “if the test evaluates to False then do nothing”. With an if -expression, on the other hand, the else part is required, since the if -expression must result in some value.

Idiomatic Haskell does not use if expressions very much, often using pattern-matching or guards instead (see the next section).

Defining basic functions

We can write functions on integers by cases.

Note the syntax for the type of a function: sumtorial :: Integer -> Integer says that sumtorial is a function which takes an Integer as input and yields another Integer as output.

Each clause is checked in order from top to bottom, and the first matching clause is chosen. For example, sumtorial 0 evaluates to 0 , since the first clause is matched. sumtorial 3 does not match the first clause ( 3 is not 0 ), so the second clause is tried. A variable like n matches anything, so the second clause matches and sumtorial 3 evaluates to 3 + sumtorial (3-1) (which can then be evaluated further).

Choices can also be made based on arbitrary Boolean expressions using guards . For example:

Any number of guards can be associated with each clause of a function definition, each of which is a Boolean expression. If the clause’s patterns match, the guards are evaluated in order from top to bottom, and the first one which evaluates to True is chosen. If none of the guards evaluate to True , matching continues with the next clause.

For example, suppose we evaluate hailstone 3 . First, 3 is matched against n , which succeeds (since a variable matches anything). Next, n `mod` 2 == 0 is evaluated; it is False since n = 3 does not result in a remainder of 0 when divided by 2 . otherwise is just an convenient synonym for True , so the second guard is chosen, and the result of hailstone 3 is thus 3*3 + 1 = 10 .

As a more complex (but more contrived) example:

What is foo (-3) ? foo 0 ? foo 1 ? foo 36 ? foo 38 ?

As a final note about Boolean expressions and guards, suppose we wanted to abstract out the test of evenness used in defining hailstone . A first attempt is shown below:

This works , but it is much too complicated. Can you see why?

We can pair things together like so:

Notice that the (x,y) notation is used both for the type of a pair and a pair value .

The elements of a pair can be extracted again with pattern matching :

Haskell also has triples, quadruples, … but you should never use them. As we’ll see next week, there are much better ways to package three or more pieces of information together.

Using functions, and multiple arguments

To apply a function to some arguments, just list the arguments after the function, separated by spaces, like this:

The above example applies the function f to the three arguments 3 , 17 , and 8 . Note also the syntax for the type of a function with multiple arguments, like Arg1Type -> Arg2Type -> ... -> ResultType . This might seem strange to you (and it should!). Why all the arrows? Wouldn’t it make more sense for the type of f to be something like Int Int Int -> Int ? Actually, the syntax is no accident: it is the way it is for a very deep and beautiful reason, which we’ll learn about in a few weeks; for now you just have to take my word for it!

Note that function application has higher precedence than any infix operators . So it would be incorrect to write

if you intend to pass n+1 as the second argument to f , because this parses as

(f 3 n) + (1 7) .

Instead, one must write

f 3 (n+1) 7 .

Lists are one of the most basic data types in Haskell.

Haskell (like Python) also has list comprehensions ; you can read about them in LYAH .

Strings are just lists of characters. That is, String is just an abbreviation for [Char] , and string literal syntax (text surrounded by double quotes) is just an abbreviation for a list of Char literals.

This means that all the standard library functions for processing lists can also be used to process String s.

Constructing lists

The simplest possible list is the empty list:

Other lists are built up from the empty list using the cons operator, (:) . Cons takes an element and a list, and produces a new list with the element prepended to the front.

We can see that [2,3,4] notation is just convenient shorthand for 2 : 3 : 4 : [] . Note also that these are really singly linked lists , NOT arrays.

We stop the hailstone sequence when we reach 1. The hailstone sequence for a general n consists of n itself, followed by the hailstone sequence for hailstone n , that is, the number obtained by applying the hailstone transformation once to n .

Functions on lists

We can write functions on lists using pattern matching .

The first clause says that the length of an empty list is 0. The second clause says that if the input list looks like (x:xs) , that is, a first element x consed onto a remaining list xs , then the length is one more than the length of xs .

Since we don’t use x at all we could also replace it by an underscore: intListLength (_:xs) = 1 + intListLength xs .

We can also use nested patterns:

Note how the last clause matches a list starting with x and followed by… a list starting with y and followed by the list zs . We don’t actually need the extra parentheses, so sumEveryTwo (x:y:zs) = ... would be equivalent.

Combining functions

It’s good Haskell style to build up more complex functions by combining many simple ones.

This may seem inefficient to you: it generates the entire hailstone sequence first and then finds its length, which wastes lots of memory… doesn’t it? Actually, it doesn’t! Because of Haskell’s lazy evaluation, each element of the sequence is only generated as needed, so the sequence generation and list length calculation are interleaved. The whole computation uses only O(1) memory, no matter how long the sequence. (Actually, this is a tiny white lie, but explaining why (and how to fix it) will have to wait a few weeks.)

We’ll learn more about Haskell’s lazy evaluation strategy in a few weeks. For now, the take-home message is: don’t be afraid to write small functions that transform whole data structures, and combine them to produce more complex functions. It may feel unnatural at first, but it’s the way to write idiomatic (and efficient) Haskell, and is actually a rather pleasant way to write programs once you get used to it.

A word about error messages

Actually, six:

Don’t be scared of error messages!

GHC’s error messages can be rather long and (seemingly) scary. However, usually they’re long not because they are obscure, but because they contain a lot of useful information! Here’s an example:

First we are told “Couldn’t match expected type [a0] with actual type Char ”. This means that something was expected to have a list type, but actually had type Char . What something? The next line tells us: it’s the first argument of (++) which is at fault, namely, 'x' . The next lines go on to give us a bit more context. Now we can see what the problem is: clearly 'x' has type Char , as the first line said. Why would it be expected to have a list type? Well, because it is used as an argument to (++) , which takes a list as its first argument.

When you get a huge error message, resist your initial impulse to run away; take a deep breath; and read it carefully. You won’t necessarily understand the entire thing, but you will probably learn a lot, and you may just get enough information to figure out what the problem is.

Generated 2013-03-14 14:39:58.567681

• Create account
• Contributions

Operator precedence

Provide a list of   precedence   and   associativity   of all the operators and constructs that the language utilizes in descending order of precedence such that an operator which is listed on some row will be evaluated prior to any operator that is listed on a row further below it.

Operators that are in the same cell (there may be several rows of operators listed in a cell) are evaluated with the same level of precedence, in the given direction.

State whether arguments are passed by value or by reference.

See 11l documentation .

In 8th it's very simple: the currently invoked word has precedence, and items are operated upon in the order they are popped off the stack.

• 6502 Assembly

There are two types of indirect addressing: Indirect X and Indirect Y. These differ in that the indirect X mode applies the offset before looking up the address.

The use of parentheses for these modes is required, and nicely illustrates the order of operations. To put it in terms of a hierarchy:

Ada Reference Manual, ISO/IEC 8652:2012(E), section 4.5. "Operators and Expression Evaluation" contains the listing.

Note: '/' is the Euclidean division

The coder may define new operators and both those and the pre-defined ones may be overloaded and their priorities may be changed.

Array, Procedure, Dereference, Selection and Generator operations

These are technically not operators, rather they are considered " units associated with names "

Monadic operators

Standard dyadic operators with associated priorities

Note: Tertiaries include names nil and ○.

Assignation and identity relations etc

Again, these are technically not operators, rather they are considered " units associated with names "

Note: Quaternaries include names skip and ~.

Algol 68 also includes (something like) C's ternary conditions, e.g.:

• case ~ in ~ ouse ~ in ~ out ~ esac or simply "( ~ | ~ |: ~ | ~ | ~ )",
• if ~ then ~ elif ~ then ~ else ~ fi or simply "( ~ | ~ |: ~ | ~ | ~ )",

And (unlike C's comma operator) the ";" can be used to indicate statements are done sequentially, where as the "," indicates that the statements can be done "collaterally", e.g. in parallel. Or a parallel clause can be used to force statements to be executed in parallel, e.g. par ( ~, ~, ... )

Key: The super scripts indicate the following:

• ALGOL 68 Rev0 indicates Algol 68 Final Report (Essentially Revision 0)
• ALGOL 68 Rev0&1 indicates Algol 68 Revised Report (Essentially Revision 1)
• ALGOL 68 C indicates Cambridge University Algol 68 [1] .
• ALGOL 68 G indicates Algol 68 Genie [2]

• AppleScript

From the AppleScript Language Guide, plus additional notes:

There is no need for operator precedence in Arturo, since all expressions are parsed/evaluated in the exact same way.

The main expression evaluation order of Arturo is right-to-left. But with a tiny asterisk: Your code will be evaluated from left to right, it is the expressions passed to your function calls that will be evaluated from right-to-left.

This works for mathematical expressions too, since they are treated as normal function calls.

See Arturo documentation .

See also: gawk-Reference

Operators are evaluated according to a strict set of rules. These rules are called the “Order of Operations”.

From the POSIX Standard , ordered by decreasing precedence:

In the table below, L indicates left associativity and R indicates right associativity.

The operators of most popular programming languages correspond to functions in BQN (all functions, builtin and defined, are infix).

However, modifiers (higher order functions) have higher precedence over functions.

Here, 2 + 1 is evaluated first:

Here, -˜ is evaluated first. ˜ flips the arguments given to a function.

A precedence table for all BQN syntax is shown below.

Bracmat has 15 binary operators and 12 unary operators, not counting the minus

The binary operators have a simple precedence order and all binary operators are right-associative.

Precedence among unary operators is a mixed bag. Unary operators can modify something that is to the right of the unary operator, which can be another unary operator, a string or a binary operator.

Of the unary operators ? and ! (or !! ), the latter have the higher priority. So 17:?!x assigns the value 17 to the variable that happens to be the value of x . (Like *x = 17 in C). (The unary operators ! and !! cannot be combined and are reduced to !! )

The negation operator ~ negates the first of the unary operators / # < > % @ that is present. If none of these unary operators is present, the negation operator negates the node (string or expression with binary operator) itself, with the meaning "not equal to". Bang operators ! or !! turn their operand into a variable that is supposed to have a value. The negation operator operates on the value (direct resp. indirect) of a variable, not on the variable name itself.

The combination ~<> has to be read in one piece, meaning "not unequal", which is not quite unequal to ~ . It is used for case insensitive matching.

Some combinations of unary operators have currently no meaning and are silently reinterpreted: ~?x is the same as ?x and ~?!x is the same as ?!x . But ~#?x is not the same as #?x .

The [ and ` (grave accent) are outside any considerations of precedence.

If you are wondering what the discussed unary operators are for, see this table:

Same as C++ .

The following is a table that lists the precedence and associativity of all the operators in the C and C++ languages. An operator's precedence is unaffected by overloading.

For quick reference, see also this equivalent, color-coded table.

MSDN documentation

• Caché ObjectScript

There is no operator precedence in COS or in MUMPS. It is evaluated left-to-right. Operations can be forced to evaluate in a specific order using parentheses. Example:

34 SAMPLES>write 18 / (2 * 3) + 7 10

As is the case with LISPs in general, there is no need to worry about operator precedence. This is one of the benefits of S-Expressions and prefix notation . All functions evaluate left to right and inside out. The operators in Clojure are just functions, and everything is fully parenthesized.

That being said, there is a macro expansion phase that precedes compilation, and with macros you have great power to change the rules. A couple of the most common macros with respect to ordering are the thread-first macro and the thread-last macro . These allow you to order expressions as a chain, which in many cases is preferable for readability.

The following data was derived from the 2009 draft COBOL 20XX Standard .

Arithmetic Expressions

Boolean Expressions

Concatenation Expressions

The & operator is the only operator used in concatenation expressions.

Logical Expressions

• Common Lisp

There is no need to worry about operator precedence in Common Lisp and Lisp's in general. Operators (like + - * / ) are normal functions and all of the code is organized as S-expressions with a prefixed polish notation. In result all of the code is parenthesized and the code is evaluated from the innermost S-expression to the outermost S-expression.

A copy from the D wiki .

As dc is a reverse-polish calculator, all operators/commands pop their arguments off the stack. They are simply evaluated in the order they appear in the code (from left to right).

See table at Free Pascal .

Ecstasy's precedence table is based loosely on the C family of languages, but with significant tweaks to support the most common patterns without parenthesis. At a given level of precedence, all evaluation is from left to right.

Official documentation: [ [3] ], section 8.28.5

Any sequence of free operators (that does not already have a defined meaning, such as = or ? ) can be used as an alias for unary or binary operations.

The set of free operators is:

Special binary aliases such as () and [] can also be used.

Refer to section 8.32.21 of the aforementioned link for more details.

Official documentation table: [ [4] ]

Because Factor uses postfix notation and relies entirely on fixed-argument function composition, all operators have the same precedence. Think of using a calculator that uses reverse-polish notation. Instead of writing (3+5)*2 , you'd write 3 5 + 2 * . There is no need for parentheses to clarify the order of operations.

Forth as the language of a stack machine does not require operator precedence. Since all arguments for operations are taken from the stack the order is simply left to right, in the order of the source code. Even the brackets used for the S-expression are not needed with reverse Polish notation.

• Fortran77 standard .
• Fortran [5]

If operators have equal precedence, they then are evaluated in the order in of their associativity. The associativity may be Left-to-Right or Right-to-Left order.

As a rule, binary operators (such as +, ^) and unary postfix operators (such as (), ->) are evaluated Left-to-Right, and unary prefix operators (such as Not, @) are evaluated Right-to-Left.

Operators that have an associativity of "N/A" indicate that there is no expression in which the operator can be used where its order of operation would need to be checked, either by precedence or by associativity. Function-like operators such as Cast are always the first to be evaluated due to the parentheses required in their syntax. And assignment operators are always the last to be evaluated.

Parentheses can be used to override operator precedence. Operations within parentheses are performed before other operations

• Free Pascal

“[B]inary operators of the same precedence are left-associative.” Nevertheless, “[t]he order in which expressions of the same precedence are evaluated is not guaranteed to be left-to-right.” (quotes from the Free Pascal Reference Guide)

The default configuration sets {$boolEval off} ( {$B-} for short). This enables “lazy evaluation” and thus affects evaluation order.

One notable difference to standardized Pascal in operator precedence can be switched: Normally, Free Pascal’s unary minus is at the highest precedence level. With {$modeSwitch ISOUnaryMinus+} , which is enabled by default in {$mode ISO} and {$mode extendedPascal} , unary minus can be put at the same level as all other adding operators (like the ISO standards define).

Furor is basically an "RPN-style" language. Thus, similarly to the Forth, Furor as the language of a stack machine does not require operator precedence. Since all arguments for operations are taken from the stack the order is simply left to right, in the order of the source code.

• FutureBasic

When an expression includes more than one operator, the order in which the operations are performed can affect the result. When an operator appears to the left or right of a parenthetical expression, all of the operations within the parentheses are performed first. When several operators all appear within the same matching pair of parentheses (or outside of all parentheses), the order in which their operations are performed is determined by their order of precedence, with "higher precedence" operations being performed before "lower precedence" ones. For example, consider this expression: 4 + 7 * 5 The "*" operator has a higher precedence than the "+" operator (see the table below). So, when this expression is evaluated, first 7 is multiplied by 5 to get 35; then that result is added to 4 to get the final answer of 39. The following table lists the operators in order of their precedence, from highest to lowest. When an expression contains several operators at the same level of precedence (and within the same depth of parentheses), their operations are always performed from left to right.

Binary operators of the same precedence associate from left to right. Associativity has no meaning for unary operators.

Syntactic elements not in the list are not considered operators in Go; if they present ambiguity in order of evaluation, the ambiguity is resolved by other rules specific to those elements.

Icon and Unicon

Taken from http://www.cs.arizona.edu/icon/refernce/exprlist.htm#expressions (blank lines separate groups of operators with equal precedence):

See http://www.jsoftware.com/help/dictionary/partsofspeech.htm for tokens in each grammatical class.

Note that other parts of speech do not have any precedence, because they are not "operators".

Note that this is an imprecise statement of the grammatical rules. For a complete treatment, see http://www.jsoftware.com/help/dictionary/dicte.htm

Here's an informal treatment of the grammar:

Conjunctions require a left and right argument, either of which may be a noun or a verb. If one argument is omitted the conjunction is curried with the remaining argument, forming an adverb (if the right argument is omitted, the precedence of the conjunction is treated as lower than the precedence of a verb -- this might be thought of as a consequence of the "long left scope" of conjunctions extending as far as possible).

Adverbs require a single left argument, which may be a noun or a verb.

Verbs require a right argument which must be a noun and may accept an optional left argument (which must also be a noun). Unless we're working with a dangling (rightmost) conjunction, verbs have lower precedence than adverbs and conjunctions. (A conjunction on the far right without a right argument is treated as having lower precedence than verbs.) That said, note that the form verb verb verb is legal - this creates a derived verb whose arguments are given to the left and right verb and their results will be the argument for the middle verb. Longer trains are treated by using this mechanism on the rightmost three verbs. A shorter train is also given special treatment (the right verb gets the right argument, the left verb gets a left argument and the result of the right verb).

Nouns are not operators and accept no arguments.

The result of a verb must be a noun.

The result of an adverb or a conjunction can have any one of these grammatical classifications, and verb results are typical (and, thus, the result of an adverb or a conjunction may accept further arguments). Adverbs and conjunctions serve a role analogous to that of macros in other languages.

This is well-documented on the Oracle website .

Mozilla Developer Network have a nice list of this at JavaScript Reference:Expressions and operators:Operator Precedence

The order of precedence of jq operators is shown in the following table, which also shows operator associativity:

• "%right" and %left" mean respectively right and left-associative;
• "%nonassoc" means it is a syntax error to find the operator twice in a row;
• "(none)" means that that no associativity is defined.

The associativity rules can be summarized:

• Operators with one of the characters "=", "<", or ">" in them are non-associative;
• "," and "//" are right-associative;
• All others are or behave as left-associative operators.

• If the expression immediately to the left of "?" raises an error, "?" suppresses it and emits nothings at all. E.g. 'error("bye")?' is equivalent to the expression 'empty'.
• Parentheses alter the order of evaluation in the usual way.
• Control structures such as if ... then ... else ... end and reduce ... as VAR (...; ...) determine the boundaries of subexpressions.

This is well-documented on the Kotlin language website .

From the LIL readme.txt documentation:

Table available here . That table does not contain all operators, however.

• Concatenation and exponentiation are right-associative, all other binary operators are left-associative
• Binding is done at the call site; therefore, method lookup is syntactically part of the call

Mathematica / Wolfram Language

Here is an outline:

There is a table of precedence of all operators on the page tutorial/OperatorInputForms in Mathematica help.

There is a table of precedence of all operators on the page [6]

min is a stack language that uses postfix notation, so for the most part, all operators have the same precedence. Sigils are a small exception. However, they de-sugar to postfix. For example, the following two lines are equivalent:

This table contains the precedence and associativity of operators and other expression constructs in OCaml, including user-defined operators.

Unary operators have the highest precedence.

There are seven precedence levels for binary and ternary operators.

Binary operators of the same precedence associate from left to right. For instance "x / y * z" is the same as "(x / y) * z"

Oforth uses RPN notation. There are not different operator precedences. Everything is evaluated left to right.

Unless otherwise stated, operators at a given level are applied left-to-right.

There are some exceptions to this standard order:

• If the short-circuit operator `&&` is used and the left expression is falsy (`0`, `[]`, etc.) then the right expression is not evaluated. Similarly, with `||` is the left is truthy then the right expression is not evaluated.
• Assignment and all of the compound assignment operators need an lvalue on the left; if there is an expression where the rightmost part is an lvalue, assignment happens first. So `1 + n = 4 + 1` first adds 4 to 1, then assigns 5 to n, then adds 1 to 5.

See the User's Guide to PARI/GP in the documentation , section 2.4, "GP operators".

Standard Pascal, as laid out in ISO standard 7185, recognizes four precedence levels. Extended Pascal (EP), defined in ISO standard 10206, has one additional level, exponentiating operators . The following is a consolidated table for both standards:

“Sequences of two or more operators of the same precedence shall be left associative.” (quote from ISO standards)

However, unlike some other programming languages, operator precedence does not define evaluation order. This is because Pascal does not permit “lazy evaluation”: Except in the case of and_then and or_else , the evaluation order implementation-defined . Some compilers, for instance the FPC ( Free Pascal Compiler), evaluate “more complex” subexpression first before evaluating “easy” subexpressions (rationale: avoid register spilling).

See the relevant documentation for a table of Perl 5 operators ordered by precedence level.

Parenthesis is required to mix and/or/xor in an expression, without said you get a compilation error because the compiler refuses to guess what you actually mean.

Perhaps surprisingly Phix does not rely on associativity, mainly because it has a power() function rather than an infix operator for that. You could alternatively say that all the above operators bar the unary ops are left associative, within their own precedence level.

Phix has reference counting with copy-on-write semantics: technically parameters are always passed by reference, which can improve performance, however attempting to modify anything with a reference count greater than one performs an internal clone (at that level) which means it behaves as if everything were being passed by value. It also has automatic pass by reference for local variables such that (eg) table = somefunc(table) does not increase the reference count (in practice the calling code's local variable becomes unassigned over the call) and consequently makes in-situ modification possible, which can obviously also significantly benefit performance. Under "with js", aka "with javascript_semantics", any said internal clone triggers a runtime error, effectively prohibiting copy-on-write semantics and thus ensuring the code is compatible with JavaScript, and in fact also implicitly banning the usual pass-by-sharing semantics of JavaScript, except where covered by the automatic pbr handling.

Operator Precedence

There is no need to worry about operator precedence in PicoLisp and Lisp's in general. All operators are normal functions and all of the code is organized as S-expressions with a prefixed polish notation.

• Plain English

Plain English treats an expression if it contains any of the operators 'plus', 'minus', 'times', 'divided by', or 'then'. Arguments in expressions are passed in by reference. Expressions are evaluated from left to right, ignoring traditional precedence rules.

For example, when evaluating 2 + 3 * 4, Plain English will calculate (2 + 3) * 4, and not 2 + (3 * 4).

Arguments are passed by value.

See this table and the whole page for details on Python version 3.x An excerpt of which is this table:

• The % operator is also used for string formatting; the same precedence applies.
• The power operator ** binds less tightly than an arithmetic or bitwise unary operator on its right, that is, 2**-1 is 0.5 .

Operators have equal precedence and expressions are evaluated from right to left.

Because Quackery uses postfix notation and relies entirely on fixed-argument function composition, all operators have the same precedence. Think of using a calculator that uses reverse-polish notation. Instead of writing (3+5)*2 , you'd write 3 5 + 2 * . There is no need for parentheses to clarify the order of operations.

Racket uses S-expr for its syntax, operators and functions show no precedences as all code is written as:

function being any function or operator (language or user defined) and arguments are the arguments passed to it.

(formerly Perl 6) See this table for a list of the precedence levels. Raku is an operator-rich language (and users may define more operators at will), so instead of listing all the operators in the table, representative operators are listed for some of the precedence levels; see later in the same file for a more complete list of predefined operators at each precedence level.

All operators are left-associated except exponentiation and Pair creation which are right-associated. Operators of the same scope and precedence will be evaluated from left-to-right. Precedence can be overridden by using parentheses, such that a + b - c <> a + (b - c).

By default, intrinsic types (Integer, String, Double, etc.) are passed by value and complex types (objects, arrays, etc.) are passed by reference. This can be overridden by using the ByVal or ByRef keyword before the parameter name in the method signature.

Ruby operators, by precedence (high to low), with arity (N), associativity (A), and definability (D)

Operator precedence is well-documented on the official Scala Documentation | Tour of Scala | Operators web page.

As with Common Lisp and Racket, Scheme uses s-expressions so there is no need for operator precedence.

e.g. an expression like "3 + 4 x 5" must be entered as either (+ 3 (* 4 5)) or (* (+ 3 4) 5)

Seed7 supports user defined operators with priority and associativity. This includes user defined operator symbols. Priority and associativity are defined with the Seed7 Structured Syntax Description ( S7SSD ) A S7SSD statement like

specifies the syntax of the + operator. The right arrow -> describes the associativity: Binding of operands from left to right. With 7 the priority of the + operator is defined. The syntax pattern

is introduced and delimited with dots ( . ). Without dots the pattern is

The symbol () is a nonterminal symbol and + is a terminal symbol. The S7SSD does not distinguish between different nonterminal symbols. Instead it only knows one nonterminal symbol: () .

The include file syntax.s7i contains the syntax of the predefined operators. The table below is extracted from syntax.s7i:

All operators in Sidef have the same precedence, which is controlled by lack of whitespace between the operands.

For example:

See also the documentation on the precedence of operators.

Modern Simula syntax:

Note: // is the Euclidean division

Smalltalk does not have operators which are built in to the language. All operations are message sends to a receiver object (aka virtual function calls). Messages are one of 3 types: unary message : no argument, alphanumeric name (highest precedence; left to right evaluation) binary message : any combination of special characters (left to right evaluation) keyword message : one or more arguments, alphanumeric name with colons (lowest precedence)

Unary message examples: negated abs conjugated size isZero Binary examples: + - * % <=> ===> ˜˜ ˜= = , ,, (yes "," (comma) and ",," are possible!) Keyword examples: min: max: at: at:put: from:to:do: bitAnd: bitOr:

Within unary and binary messages, evaluation is strictly left to right. Keyword messages must be parenthesized.

No table can be presented here: there are too many such operators, and they can also be freely added by the programmer (i.e. you may define your own "Number fooBar" or "Number +-+-+ arg" messages (if it makes any sense to you).

Math expressions are usually parenthesized for better readability (by beginners):

• Standard ML

Tcl only supports operators within an expression context (such as the expr command, which lists the operators with more detail):

• TI-83 BASIC

note : no operator between 2 symbols means an implied multiplication, so priority 6 and left to right associativity note : NOT is not an operator, it is a function: not() Examples :

Let's not the difference with Visual Basic on unary operator priority.

• Visual Basic

• Visual Basic .NET

See Visual Basic Note: the Imp and Eqv VB6 operators were been removed from Visual Basic .NET.

The following table is reproduced from the language documentation.

Arguments are passed by value though where the argument is a reference (anything other than numbers, booleans or null) this will, of course, copy the reference and not the data it refers to.

All operations of equal precedence are evaluated (associate) left-to-right.

All operations of equal precedence are evaluated (associate) left-to-right. If shared with C it has the same precedence except for logical and/or, which have the same precedence.

• Programming Tasks
• Solutions by Programming Task
• WikipediaSourced
• Mathematica
• Wolfram Language
• Phix/basics
• Pages with syntax highlighting errors
• Toggle limited content width

• Table of contents

Higher order functions

Haskell functions can take functions as parameters and return functions as return values. A function that does either of those is called a higher order function. Higher order functions aren't just a part of the Haskell experience, they pretty much are the Haskell experience. It turns out that if you want to define computations by defining what stuff is instead of defining steps that change some state and maybe looping them, higher order functions are indispensable. They're a really powerful way of solving problems and thinking about programs.

Curried functions

Every function in Haskell officially only takes one parameter. So how is it possible that we defined and used several functions that take more than one parameter so far? Well, it's a clever trick! All the functions that accepted several parameters so far have been curried functions . What does that mean? You'll understand it best on an example. Let's take our good friend, the max function. It looks like it takes two parameters and returns the one that's bigger. Doing max 4 5 first creates a function that takes a parameter and returns either 4 or that parameter, depending on which is bigger. Then, 5 is applied to that function and that function produces our desired result. That sounds like a mouthful but it's actually a really cool concept. The following two calls are equivalent:

Putting a space between two things is simply function application . The space is sort of like an operator and it has the highest precedence. Let's examine the type of max . It's max :: (Ord a) => a -> a -> a . That can also be written as max :: (Ord a) => a -> (a -> a) . That could be read as: max takes an a and returns (that's the -> ) a function that takes an a and returns an a . That's why the return type and the parameters of functions are all simply separated with arrows.

So how is that beneficial to us? Simply speaking, if we call a function with too few parameters, we get back a partially applied function, meaning a function that takes as many parameters as we left out. Using partial application (calling functions with too few parameters, if you will) is a neat way to create functions on the fly so we can pass them to another function or to seed them with some data.

Take a look at this offensively simple function:

What really happens when we do multThree 3 5 9 or ((multThree 3) 5) 9 ? First, 3 is applied to multThree , because they're separated by a space. That creates a function that takes one parameter and returns a function. So then 5 is applied to that, which creates a function that will take a parameter and multiply it by 15. 9 is applied to that function and the result is 135 or something. Remember that this function's type could also be written as multThree :: (Num a) => a -> (a -> (a -> a)) . The thing before the -> is the parameter that a function takes and the thing after it is what it returns. So our function takes an a and returns a function of type (Num a) => a -> (a -> a) . Similarly, this function takes an a and returns a function of type (Num a) => a -> a . And this function, finally, just takes an a and returns an a . Take a look at this:

By calling functions with too few parameters, so to speak, we're creating new functions on the fly. What if we wanted to create a function that takes a number and compares it to 100 ? We could do something like this:

If we call it with 99 , it returns a GT . Simple stuff. Notice that the x is on the right hand side on both sides of the equation. Now let's think about what compare 100 returns. It returns a function that takes a number and compares it with 100 . Wow! Isn't that the function we wanted? We can rewrite this as:

The type declaration stays the same, because compare 100 returns a function. Compare has a type of (Ord a) => a -> (a -> Ordering) and calling it with 100 returns a (Num a, Ord a) => a -> Ordering . The additional class constraint sneaks up there because 100 is also part of the Num typeclass.

Infix functions can also be partially applied by using sections. To section an infix function, simply surround it with parentheses and only supply a parameter on one side. That creates a function that takes one parameter and then applies it to the side that's missing an operand. An insultingly trivial function:

Calling, say, divideByTen 200 is equivalent to doing 200 / 10 , as is doing (/10) 200 . A function that checks if a character supplied to it is an uppercase letter:

The only special thing about sections is using - . From the definition of sections, (-4) would result in a function that takes a number and subtracts 4 from it. However, for convenience, (-4) means minus four. So if you want to make a function that subtracts 4 from the number it gets as a parameter, partially apply the subtract function like so: (subtract 4) .

What happens if we try to just do multThree 3 4 in GHCI instead of binding it to a name with a let or passing it to another function?

GHCI is telling us that the expression produced a function of type a -> a but it doesn't know how to print it to the screen. Functions aren't instances of the Show typeclass, so we can't get a neat string representation of a function. When we do, say, 1 + 1 at the GHCI prompt, it first calculates that to 2 and then calls show on 2 to get a textual representation of that number. And the textual representation of 2 is just the string "2" , which then gets printed to our screen.

Some higher-orderism is in order

Functions can take functions as parameters and also return functions. To illustrate this, we're going to make a function that takes a function and then applies it twice to something!

First of all, notice the type declaration. Before, we didn't need parentheses because -> is naturally right-associative. However, here, they're mandatory. They indicate that the first parameter is a function that takes something and returns that same thing. The second parameter is something of that type also and the return value is also of the same type. We could read this type declaration in the curried way, but to save ourselves a headache, we'll just say that this function takes two parameters and returns one thing. The first parameter is a function (of type a -> a ) and the second is that same a . The function can also be Int -> Int or String -> String or whatever. But then, the second parameter to also has to be of that type.

The body of the function is pretty simple. We just use the parameter f as a function, applying x to it by separating them with a space and then applying the result to f again. Anyway, playing around with the function:

The awesomeness and usefulness of partial application is evident. If our function requires us to pass it a function that takes only one parameter, we can just partially apply a function to the point where it takes only one parameter and then pass it.

Now we're going to use higher order programming to implement a really useful function that's in the standard library. It's called zipWith . It takes a function and two lists as parameters and then joins the two lists by applying the function between corresponding elements. Here's how we'll implement it:

Look at the type declaration. The first parameter is a function that takes two things and produces a third thing. They don't have to be of the same type, but they can. The second and third parameter are lists. The result is also a list. The first has to be a list of a 's, because the joining function takes a 's as its first argument. The second has to be a list of b 's, because the second parameter of the joining function is of type b . The result is a list of c 's. If the type declaration of a function says it accepts an a -> b -> c function as a parameter, it will also accept an a -> a -> a function, but not the other way around! Remember that when you're making functions, especially higher order ones, and you're unsure of the type, you can just try omitting the type declaration and then checking what Haskell infers it to be by using :t .

The action in the function is pretty similar to the normal zip . The edge conditions are the same, only there's an extra argument, the joining function, but that argument doesn't matter in the edge conditions, so we just use a _ for it. And function body at the last pattern is also similar to zip , only it doesn't do (x,y) , but f x y . A single higher order function can be used for a multitude of different tasks if it's general enough. Here's a little demonstration of all the different things our zipWith' function can do:

As you can see, a single higher order function can be used in very versatile ways. Imperative programming usually uses stuff like for loops, while loops, setting something to a variable, checking its state, etc. to achieve some behavior and then wrap it around an interface, like a function. Functional programming uses higher order functions to abstract away common patterns, like examining two lists in pairs and doing something with those pairs or getting a set of solutions and eliminating the ones you don't need.

We'll implement another function that's already in the standard library, called flip . Flip simply takes a function and returns a function that is like our original function, only the first two arguments are flipped. We can implement it like so:

Reading the type declaration, we say that it takes a function that takes an a and a b and returns a function that takes a b and an a . But because functions are curried by default, the second pair of parentheses is really unnecessary, because -> is right associative by default. (a -> b -> c) -> (b -> a -> c) is the same as (a -> b -> c) -> (b -> (a -> c)) , which is the same as (a -> b -> c) -> b -> a -> c . We wrote that g x y = f y x . If that's true, then f y x = g x y must also hold, right? Keeping that in mind, we can define this function in an even simpler manner.

Here, we take advantage of the fact that functions are curried. When we call flip' f without the parameters y and x , it will return an f that takes those two parameters but calls them flipped. Even though flipped functions are usually passed to other functions, we can take advantage of currying when making higher-order functions by thinking ahead and writing what their end result would be if they were called fully applied.

Maps and filters

map takes a function and a list and applies that function to every element in the list, producing a new list. Let's see what its type signature is and how it's defined.

The type signature says that it takes a function that takes an a and returns a b , a list of a 's and returns a list of b 's. It's interesting that just by looking at a function's type signature, you can sometimes tell what it does. map is one of those really versatile higher-order functions that can be used in millions of different ways. Here it is in action:

You've probably noticed that each of these could be achieved with a list comprehension. map (+3) [1,5,3,1,6] is the same as writing [x+3 | x <- [1,5,3,1,6]] . However, using map is much more readable for cases where you only apply some function to the elements of a list, especially once you're dealing with maps of maps and then the whole thing with a lot of brackets can get a bit messy.

filter is a function that takes a predicate (a predicate is a function that tells whether something is true or not, so in our case, a function that returns a boolean value) and a list and then returns the list of elements that satisfy the predicate. The type signature and implementation go like this:

Pretty simple stuff. If p x evaluates to True , the element gets included in the new list. If it doesn't, it stays out. Some usage examples:

All of this could also be achived with list comprehensions by the use of predicates. There's no set rule for when to use map and filter versus using list comprehension, you just have to decide what's more readable depending on the code and the context. The filter equivalent of applying several predicates in a list comprehension is either filtering something several times or joining the predicates with the logical && function.

Remember our quicksort function from the previous chapter ? We used list comprehensions to filter out the list elements that are smaller than (or equal to) and larger than the pivot. We can achieve the same functionality in a more readable way by using filter :

Mapping and filtering is the bread and butter of every functional programmer's toolbox. Uh. It doesn't matter if you do it with the map and filter functions or list comprehensions. Recall how we solved the problem of finding right triangles with a certain circumference. With imperative programming, we would have solved it by nesting three loops and then testing if the current combination satisfies a right triangle and if it has the right perimeter. If that's the case, we would have printed it out to the screen or something. In functional programming, that pattern is achieved with mapping and filtering. You make a function that takes a value and produces some result. We map that function over a list of values and then we filter the resulting list out for the results that satisfy our search. Thanks to Haskell's laziness, even if you map something over a list several times and filter it several times, it will only pass over the list once.

Let's find the largest number under 100,000 that's divisible by 3829 . To do that, we'll just filter a set of possibilities in which we know the solution lies.

We first make a list of all numbers lower than 100,000, descending. Then we filter it by our predicate and because the numbers are sorted in a descending manner, the largest number that satisfies our predicate is the first element of the filtered list. We didn't even need to use a finite list for our starting set. That's laziness in action again. Because we only end up using the head of the filtered list, it doesn't matter if the filtered list is finite or infinite. The evaluation stops when the first adequate solution is found.

Next up, we're going to find the sum of all odd squares that are smaller than 10,000 . But first, because we'll be using it in our solution, we're going to introduce the takeWhile function. It takes a predicate and a list and then goes from the beginning of the list and returns its elements while the predicate holds true. Once an element is found for which the predicate doesn't hold, it stops. If we wanted to get the first word of the string "elephants know how to party" , we could do takeWhile (/=' ') "elephants know how to party" and it would return "elephants" . Okay. The sum of all odd squares that are smaller than 10,000. First, we'll begin by mapping the (^2) function to the infinite list [1..] . Then we filter them so we only get the odd ones. And then, we'll take elements from that list while they are smaller than 10,000. Finally, we'll get the sum of that list. We don't even have to define a function for that, we can do it in one line in GHCI:

Awesome! We start with some initial data (the infinite list of all natural numbers) and then we map over it, filter it and cut it until it suits our needs and then we just sum it up. We could have also written this using list comprehensions:

It's a matter of taste as to which one you find prettier. Again, Haskell's property of laziness is what makes this possible. We can map over and filter an infinite list, because it won't actually map and filter it right away, it'll delay those actions. Only when we force Haskell to show us the sum does the sum function say to the takeWhile that it needs those numbers. takeWhile forces the filtering and mapping to occur, but only until a number greater than or equal to 10,000 is encountered.

For our next problem, we'll be dealing with Collatz sequences. We take a natural number. If that number is even, we divide it by two. If it's odd, we multiply it by 3 and then add 1 to that. We take the resulting number and apply the same thing to it, which produces a new number and so on. In essence, we get a chain of numbers. It is thought that for all starting numbers, the chains finish at the number 1. So if we take the starting number 13, we get this sequence: 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 . 13*3 + 1 equals 40. 40 divided by 2 is 20, etc. We see that the chain has 10 terms.

Now what we want to know is this: for all starting numbers between 1 and 100, how many chains have a length greater than 15? First off, we'll write a function that produces a chain:

Because the chains end at 1, that's the edge case. This is a pretty standard recursive function.

Yay! It seems to be working correctly. And now, the function that tells us the answer to our question:

We map the chain function to [1..100] to get a list of chains, which are themselves represented as lists. Then, we filter them by a predicate that just checks whether a list's length is longer than 15. Once we've done the filtering, we see how many chains are left in the resulting list.

Using map , we can also do stuff like map (*) [0..] , if not for any other reason than to illustrate how currying works and how (partially applied) functions are real values that you can pass around to other functions or put into lists (you just can't turn them to strings). So far, we've only mapped functions that take one parameter over lists, like map (*2) [0..] to get a list of type (Num a) => [a] , but we can also do map (*) [0..] without a problem. What happens here is that the number in the list is applied to the function * , which has a type of (Num a) => a -> a -> a . Applying only one parameter to a function that takes two parameters returns a function that takes one parameter. If we map * over the list [0..] , we get back a list of functions that only take one parameter, so (Num a) => [a -> a] . map (*) [0..] produces a list like the one we'd get by writing [(0*),(1*),(2*),(3*),(4*),(5*).. .

Getting the element with the index 4 from our list returns a function that's equivalent to (4*) . And then, we just apply 5 to that function. So that's like writing (4*) 5 or just 4 * 5 .

Lambdas are basically anonymous functions that are used because we need some functions only once. Normally, we make a lambda with the sole purpose of passing it to a higher-order function. To make a lambda, we write a \ (because it kind of looks like the greek letter lambda if you squint hard enough) and then we write the parameters, separated by spaces. After that comes a -> and then the function body. We usually surround them by parentheses, because otherwise they extend all the way to the right.

If you look about 5 inches up, you'll see that we used a where binding in our numLongChains function to make the isLong function for the sole purpose of passing it to filter . Well, instead of doing that, we can use a lambda:

Lambdas are expressions, that's why we can just pass them like that. The expression (\xs -> length xs > 15) returns a function that tells us whether the length of the list passed to it is greater than 15.

People who are not well acquainted with how currying and partial application works often use lambdas where they don't need to. For instance, the expressions map (+3) [1,6,3,2] and map (\x -> x + 3) [1,6,3,2] are equivalent since both (+3) and (\x -> x + 3) are functions that take a number and add 3 to it. Needless to say, making a lambda in this case is stupid since using partial application is much more readable.

Like normal functions, lambdas can take any number of parameters:

And like normal functions, you can pattern match in lambdas. The only difference is that you can't define several patterns for one parameter, like making a [] and a (x:xs) pattern for the same parameter and then having values fall through. If a pattern matching fails in a lambda, a runtime error occurs, so be careful when pattern matching in lambdas!

Lambdas are normally surrounded by parentheses unless we mean for them to extend all the way to the right. Here's something interesting: due to the way functions are curried by default, these two are equivalent:

If we define a function like this, it's obvious why the type declaration is what it is. There are three -> 's in both the type declaration and the equation. But of course, the first way to write functions is far more readable, the second one is pretty much a gimmick to illustrate currying.

However, there are times when using this notation is cool. I think that the flip function is the most readable when defined like so:

Even though that's the same as writing flip' f x y = f y x , we make it obvious that this will be used for producing a new function most of the time. The most common use case with flip is calling it with just the function parameter and then passing the resulting function on to a map or a filter. So use lambdas in this way when you want to make it explicit that your function is mainly meant to be partially applied and passed on to a function as a parameter.

Only folds and horses

Back when we were dealing with recursion, we noticed a theme throughout many of the recursive functions that operated on lists. Usually, we'd have an edge case for the empty list. We'd introduce the x:xs pattern and then we'd do some action that involves a single element and the rest of the list. It turns out this is a very common pattern, so a couple of very useful functions were introduced to encapsulate it. These functions are called folds. They're sort of like the map function, only they reduce the list to some single value.

A fold takes a binary function, a starting value (I like to call it the accumulator) and a list to fold up. The binary function itself takes two parameters. The binary function is called with the accumulator and the first (or last) element and produces a new accumulator. Then, the binary function is called again with the new accumulator and the now new first (or last) element, and so on. Once we've walked over the whole list, only the accumulator remains, which is what we've reduced the list to.

First let's take a look at the foldl function, also called the left fold. It folds the list up from the left side. The binary function is applied between the starting value and the head of the list. That produces a new accumulator value and the binary function is called with that value and the next element, etc.

Let's implement sum again, only this time, we'll use a fold instead of explicit recursion.

Testing, one two three:

Let's take an in-depth look into how this fold happens. \acc x -> acc + x is the binary function. 0 is the starting value and xs is the list to be folded up. Now first, 0 is used as the acc parameter to the binary function and 3 is used as the x (or the current element) parameter. 0 + 3 produces a 3 and it becomes the new accumulator value, so to speak. Next up, 3 is used as the accumulator value and 5 as the current element and 8 becomes the new accumulator value. Moving forward, 8 is the accumulator value, 2 is the current element, the new accumulator value is 10 . Finally, that 10 is used as the accumulator value and 1 as the current element, producing an 11 . Congratulations, you've done a fold!

This professional diagram on the left illustrates how a fold happens, step by step (day by day!). The greenish brown number is the accumulator value. You can see how the list is sort of consumed up from the left side by the accumulator. Om nom nom nom! If we take into account that functions are curried, we can write this implementation ever more succinctly, like so:

The lambda function (\acc x -> acc + x) is the same as (+) . We can omit the xs as the parameter because calling foldl (+) 0 will return a function that takes a list. Generally, if you have a function like foo a = bar b a , you can rewrite it as foo = bar b , because of currying.

Anyhoo, let's implement another function with a left fold before moving on to right folds. I'm sure you all know that elem checks whether a value is part of a list so I won't go into that again (whoops, just did!). Let's implement it with a left fold.

Well, well, well, what do we have here? The starting value and accumulator here is a boolean value. The type of the accumulator value and the end result is always the same when dealing with folds. Remember that if you ever don't know what to use as a starting value, it'll give you some idea. We start off with False . It makes sense to use False as a starting value. We assume it isn't there. Also, if we call a fold on an empty list, the result will just be the starting value. Then we check the current element is the element we're looking for. If it is, we set the accumulator to True . If it's not, we just leave the accumulator unchanged. If it was False before, it stays that way because this current element is not it. If it was True , we leave it at that.

The right fold, foldr works in a similar way to the left fold, only the accumulator eats up the values from the right. Also, the left fold's binary function has the accumulator as the first parameter and the current value as the second one (so \acc x -> ... ), the right fold's binary function has the current value as the first parameter and the accumulator as the second one (so \x acc -> ... ). It kind of makes sense that the right fold has the accumulator on the right, because it folds from the right side.

The accumulator value (and hence, the result) of a fold can be of any type. It can be a number, a boolean or even a new list. We'll be implementing the map function with a right fold. The accumulator will be a list, we'll be accumulating the mapped list element by element. From that, it's obvious that the starting element will be an empty list.

If we're mapping (+3) to [1,2,3] , we approach the list from the right side. We take the last element, which is 3 and apply the function to it, which ends up being 6 . Then, we prepend it to the accumulator, which is was [] . 6:[] is [6] and that's now the accumulator. We apply (+3) to 2 , that's 5 and we prepend ( : ) it to the accumulator, so the accumulator is now [5,6] . We apply (+3) to 1 and prepend that to the accumulator and so the end value is [4,5,6] .

Of course, we could have implemented this function with a left fold too. It would be map' f xs = foldl (\acc x -> acc ++ [f x]) [] xs , but the thing is that the ++ function is much more expensive than : , so we usually use right folds when we're building up new lists from a list.

If you reverse a list, you can do a right fold on it just like you would have done a left fold and vice versa. Sometimes you don't even have to do that. The sum function can be implemented pretty much the same with a left and right fold. One big difference is that right folds work on infinite lists, whereas left ones don't! To put it plainly, if you take an infinite list at some point and you fold it up from the right, you'll eventually reach the beginning of the list. However, if you take an infinite list at a point and you try to fold it up from the left, you'll never reach an end!

Folds can be used to implement any function where you traverse a list once, element by element, and then return something based on that. Whenever you want to traverse a list to return something, chances are you want a fold. That's why folds are, along with maps and filters, one of the most useful types of functions in functional programming.

The foldl1 and foldr1 functions work much like foldl and foldr , only you don't need to provide them with an explicit starting value. They assume the first (or last) element of the list to be the starting value and then start the fold with the element next to it. With that in mind, the sum function can be implemented like so: sum = foldl1 (+) . Because they depend on the lists they fold up having at least one element, they cause runtime errors if called with empty lists. foldl and foldr , on the other hand, work fine with empty lists. When making a fold, think about how it acts on an empty list. If the function doesn't make sense when given an empty list, you can probably use a foldl1 or foldr1 to implement it.

Just to show you how powerful folds are, we're going to implement a bunch of standard library functions by using folds:

head is better implemented by pattern matching, but this just goes to show, you can still achieve it by using folds. Our reverse' definition is pretty clever, I think. We take a starting value of an empty list and then approach our list from the left and just prepend to our accumulator. In the end, we build up a reversed list. \acc x -> x : acc kind of looks like the : function, only the parameters are flipped. That's why we could have also written our reverse as foldl (flip (:)) [] .

Another way to picture right and left folds is like this: say we have a right fold and the binary function is f and the starting value is z . If we're right folding over the list [3,4,5,6] , we're essentially doing this: f 3 (f 4 (f 5 (f 6 z))) . f is called with the last element in the list and the accumulator, that value is given as the accumulator to the next to last value and so on. If we take f to be + and the starting accumulator value to be 0 , that's 3 + (4 + (5 + (6 + 0))) . Or if we write + as a prefix function, that's (+) 3 ((+) 4 ((+) 5 ((+) 6 0))) . Similarly, doing a left fold over that list with g as the binary function and z as the accumulator is the equivalent of g (g (g (g z 3) 4) 5) 6 . If we use flip (:) as the binary function and [] as the accumulator (so we're reversing the list), then that's the equivalent of flip (:) (flip (:) (flip (:) (flip (:) [] 3) 4) 5) 6 . And sure enough, if you evaluate that expression, you get [6,5,4,3] .

scanl and scanr are like foldl and foldr , only they report all the intermediate accumulator states in the form of a list. There are also scanl1 and scanr1 , which are analogous to foldl1 and foldr1 .

When using a scanl , the final result will be in the last element of the resulting list while a scanr will place the result in the head.

Scans are used to monitor the progression of a function that can be implemented as a fold. Let's answer us this question: How many elements does it take for the sum of the roots of all natural numbers to exceed 1000? To get the squares of all natural numbers, we just do map sqrt [1..] . Now, to get the sum, we could do a fold, but because we're interested in how the sum progresses, we're going to do a scan. Once we've done the scan, we just see how many sums are under 1000. The first sum in the scanlist will be 1, normally. The second will be 1 plus the square root of 2. The third will be that plus the square root of 3. If there are X sums under 1000, then it takes X+1 elements for the sum to exceed 1000.

We use takeWhile here instead of filter because filter doesn't work on infinite lists. Even though we know the list is ascending, filter doesn't, so we use takeWhile to cut the scanlist off at the first occurence of a sum greater than 1000.

Function application with $

Alright, next up, we'll take a look at the $ function, also called function application . First of all, let's check out how it's defined:

What the heck? What is this useless operator? It's just function application! Well, almost, but not quite! Whereas normal function application (putting a space between two things) has a really high precedence, the $ function has the lowest precedence. Function application with a space is left-associative (so f a b c is the same as ((f a) b) c) ), function application with $ is right-associative.

That's all very well, but how does this help us? Most of the time, it's a convenience function so that we don't have to write so many parentheses. Consider the expression sum (map sqrt [1..130]) . Because $ has such a low precedence, we can rewrite that expression as sum $ map sqrt [1..130] , saving ourselves precious keystrokes! When a $ is encountered, the expression on its right is applied as the parameter to the function on its left. How about sqrt 3 + 4 + 9 ? This adds together 9, 4 and the square root of 3. If we want get the square root of 3 + 4 + 9 , we'd have to write sqrt (3 + 4 + 9) or if we use $ we can write it as sqrt $ 3 + 4 + 9 because $ has the lowest precedence of any operator. That's why you can imagine a $ being sort of the equivalent of writing an opening parentheses and then writing a closing one on the far right side of the expression.

How about sum (filter (> 10) (map (*2) [2..10])) ? Well, because $ is right-associative, f (g (z x)) is equal to f $ g $ z x . And so, we can rewrite sum (filter (> 10) (map (*2) [2..10])) as sum $ filter (> 10) $ map (*2) [2..10] .

But apart from getting rid of parentheses, $ means that function application can be treated just like another function. That way, we can, for instance, map function application over a list of functions.

Function composition

In Haskell, function composition is pretty much the same thing. We do function composition with the . function, which is defined like so:

Mind the type declaration. f must take as its parameter a value that has the same type as g 's return value. So the resulting function takes a parameter of the same type that g takes and returns a value of the same type that f returns. The expression negate . (* 3) returns a function that takes a number, multiplies it by 3 and then negates it.

One of the uses for function composition is making functions on the fly to pass to other functions. Sure, can use lambdas for that, but many times, function composition is clearer and more concise. Say we have a list of numbers and we want to turn them all into negative numbers. One way to do that would be to get each number's absolute value and then negate it, like so:

Notice the lambda and how it looks like the result function composition. Using function composition, we can rewrite that as:

Fabulous! Function composition is right-associative, so we can compose many functions at a time. The expression f (g (z x)) is equivalent to (f . g . z) x . With that in mind, we can turn

But what about functions that take several parameters? Well, if we want to use them in function composition, we usually have to partially apply them just so much that each function takes just one parameter. sum (replicate 5 (max 6.7 8.9)) can be rewritten as (sum . replicate 5 . max 6.7) 8.9 or as sum . replicate 5 . max 6.7 $ 8.9 . What goes on in here is this: a function that takes what max 6.7 takes and applies replicate 5 to it is created. Then, a function that takes the result of that and does a sum of it is created. Finally, that function is called with 8.9 . But normally, you just read that as: apply 8.9 to max 6.7 , then apply replicate 5 to that and then apply sum to that. If you want to rewrite an expression with a lot of parentheses by using function composition, you can start by putting the last parameter of the innermost function after a $ and then just composing all the other function calls, writing them without their last parameter and putting dots between them. If you have replicate 100 (product (map (*3) (zipWith max [1,2,3,4,5] [4,5,6,7,8]))) , you can write it as replicate 100 . product . map (*3) . zipWith max [1,2,3,4,5] $ [4,5,6,7,8] . If the expression ends with three parentheses, chances are that if you translate it into function composition, it'll have three composition operators.

Another common use of function composition is defining functions in the so-called point free style (also called the point less style). Take for example this function that we wrote earlier:

The xs is exposed on both right sides. Because of currying, we can omit the xs on both sides, because calling foldl (+) 0 creates a function that takes a list. Writing the function as sum' = foldl (+) 0 is called writing it in point free style. How would we write this in point free style?

We can't just get rid of the x on both right right sides. The x in the function body has parentheses after it. cos (max 50) wouldn't make sense. You can't get the cosine of a function. What we can do is express fn as a composition of functions.

Excellent! Many times, a point free style is more readable and concise, because it makes you think about functions and what kind of functions composing them results in instead of thinking about data and how it's shuffled around. You can take simple functions and use composition as glue to form more complex functions. However, many times, writing a function in point free style can be less readable if a function is too complex. That's why making long chains of function composition is discouraged, although I plead guilty of sometimes being too composition-happy. The prefered style is to use let bindings to give labels to intermediary results or split the problem into sub-problems and then put it together so that the function makes sense to someone reading it instead of just making a huge composition chain.

In the section about maps and filters, we solved a problem of finding the sum of all odd squares that are smaller than 10,000. Here's what the solution looks like when put into a function.

Being such a fan of function composition, I would have probably written that like this:

However, if there was a chance of someone else reading that code, I would have written it like this:

It wouldn't win any code golf competition, but someone reading the function will probably find it easier to read than a composition chain.

• 383summer2019 documentation »

Assignment 4: Haskell ¶

For this assignment, please follow these rules:

Don’t import any Haskell modules. Use only the functions from the standard prelude. You can write helper functions as long as they use only standard prelude functions.

The one exception is QuickTest : you can use that to help test your functions. Indeed, you are strongly encouraged to use it.

If a type signature is not given in a question, then include the most general correct type signature for each function you write. It may be necessary to use type classes.

Don’t change the names (or types) of any of the functions — otherwise the marking software will give you 0!

Figure out these problems yourself . Don’t use any substantial code that originates from books, websites or other people. If you do, you must cite the source of the code or ideas.

You don’t need to do any substantial error-checking (unless a question specifically says you should). You can assume obvious pre-conditions hold for inputs.

Please format your code beautifully and consistently , and use source code comments to explain any tricky or confusing parts. Code that is very difficult to read may lose marks.

When it is time to submit your work, please put all your functions into a file named a3.hs and submit it on Canvas .

Basic Functions ¶

(1 mark) The snoc x lst function returns a new list that is the same as lst , except x has been added to the end of it. It has this signature:

For example, snoc 5 [1,2,3] is [1,2,3,5] , and snoc 's' "cat" is "cats" .

Implement snoc using only basic recursion. Do not use ++ or reverse or any other such high-level functions.

(1 mark) Write your own version of the Haskell append operator ++ with this signature:

Of course, don’t use functions like ++ or concat in your answer.

(1 mark) Write your own version of reverse with this signature:

Don’t use any non-trivial functions in your answer unless you write those functions yourself.

(1 mark) Write a function called count_emirps n that returns the number of emirps less than, or equal to, n .

An emirp is a prime number that is a different prime when its digits are reversed. For example, 107 is an emirp because 107 is prime, and its reverse, 701, is a different prime. However, 7 and 101 are not emirps because while their reverses are primes, they are not different primes.

The first few emirps are: 13, 17, 31, 37, 71, 73, ….

count_emirps has this signature:

For example, count_emirps 100 returns 8, and count_emirps 1000 returns 36. If n is less than 13, count_emirps n returns 0.

(1 mark) Write a function called biggest_sum that takes a list of one, or more, integer lists as input, and returns the list with the greatest sum. It has this signature:

For example, biggest_sum [[2,5], [-1,3,4], [2]] returns [2,5] .

You can assume the list passed to biggest_sum is non-empty.

If one, or more more, lists are tied for the biggest sum, then return the first one.

(1 mark) Write a function called greatest , which has the following signature:

greatest f seq returns the item in seq that maximizes function f . For example:

If more than one item maximizes f , then greatest f returns the first one.

Basic Bits ¶

(1 mark) Write a function called is_bit x that returns True when x is 0 or 1, and False otherwise.

Assume x is of type Int , and the type of the returned value is Bool .

Include the most general type signature.

(1 mark) Write a function called flip_bit x that returns 1 if x is 0, and 0 if x is 1. If x is not a bit, then call error msg , where msg is a helpful error message string.

Assume x is of type Int , and the type of the returned value is also Int .

In each of the following functions, x is a list of Int values, and the returned value has type Bool . Include the most general type signature for each function.

(1 mark) Write a function called is_bit_seq1 x that returns True if x is the empty list, or if it contains only bits (as determined by is_bit ). It should return False otherwise.

Use recursion and guarded commands in your solution.

(1 mark) Re-do the previous question, except this time name the function is_bit_seq2 x , and use recursion and at least one if-then-else expression in your solution. Don’t use any guarded commands.

(1 mark) Re-do the previous question, except this time name the function is_bit_seq3 x , and don’t use recursion, guarded commands, or if- then-else in your solution. Instead, use a higher-order function to calculate the answer in one expression.

In each of the following functions, x is a list of Int values, and the type of the returned value is also a list of Int . Include the most general type signature for each function.

(1 mark) Write a function called invert_bits1 x that returns a sequence of bits that is the same as x , except 0s become 1s and 1s become 0s. For example, invert_bits1 [0,1,1,0] returns [1,0,0,1] .

Use basic recursion in your solution.

(1 mark) Re-do the previous question, but name the function invert_bits2 x , and implement it using the map function (and no recursion).

(1 mark) Re-do the previous question, but name the function invert_bits3 x , and implement it using a list comprehension (and no recursion, and no map function).

(1 mark) Write a function called bit_count x that returns a pair of values indicating the number of 0s and 1s in x . For example, bit_count [1,1,0,1] returns the pair (1, 3) , meaning there is one 0 and three 1s in the list.

Assume x is a list of Int values, and only contains bits. The type of the returned value is (Int, Int) .

(1 mark) Write a function called all_basic_bit_seqs n that returns a list of all bit sequences of length n. The order of the sequences doesn’t matter. If n is less than 1, then return an empty list.

Assume n is an Int , and the returned value is a list of Int lists.

A Custom List Data Type ¶

Haskell has good built-in support for lists that you should use for most programs. In this question we will implement our own list type as follows:

This is an algebraic data type . It defines a type called List a , that represents a list of 0, or more, values of type a . A List a is either Empty , or it is of the form (Cons first rest) , where first is of type a , and rest is of type List a . This mimics the common “cons cell” implementation of a list in a language like Lisp .

The line deriving Show is added as a convenience: it lets Haskell convert a List a to a string for printing.

(1 mark) Implement toList :: [a] -> List a , which converts a regular Haskell list to a List a . For example:

(1 mark) Implement toHaskellList :: List a -> [a] , which converts a List a to a regular Haskell list. For example:

For the following questions, don’t use toList or toHaskellList in your implementations. Only use them for testing and debugging. Stick to basic recursion and Haskell prelude functions for your solution code.

Make sure to give the most general type signatures for each of the functions.

(1 mark) Implement append A B , that returns a new List a that consists of all the elements of A followed by all the elements of B . In other words, it does for List a what ++ does for regular Haskell lists. For example:

(1 mark) Implement the function removeAll f L that returns a List a that is the same as L but all items satisfying f (i.e. for which f returns True ) have been removed. f is a predicate function of type a -> Bool and L has type List a .

For example:

(1 mark) Implement sort L , where L has type List a , that returns a new List a that is a sorted version of L (in ascending order). Use either quicksort or mergesort.

It must have this type signature:

Ord a => means that the type a must be usable with comparisons functions such as < , <= , == , etc.

Table Of Contents

• Basic Functions
• A Custom List Data Type

Previous topic

Assignment 2: An Expression Evaluator and Simplifier

Assignment 4: A Postfix Calculator in Haskell

Quick search

Ground fire in a Tupolev TU-154A in Novosibirsk