What does the asterisk in (x*) do in Haskell?

Question

I'm new to Haskell, can someone please explain to me how this code works?

f = g (\x -> x)
g k [] = k 100
g k (x:xs) = g ((x*) . k) xs

When I call f [1..5] it returns 12000. I don't understand why. What does (x*) do?

Answer 1

You can expand the definitions, and observe what's going on.

f [1..5]
= g (\x -> x) [1..5]
= g ((1*) . (\x -> x)) [2..5]
= g ((2*) . (1*) . (\x -> x)) [3..5]
= g ((3*) . (2*) . (1*) . (\x -> x)) [4..5]
= g ((4*) . (3*) . (2*) . (1*) . (\x -> x)) [5]
= g ((4*) . (3*) . (2*) . (1*) . (\x -> x)) [5]
= g ((5*) . (4*) . (3*) . (2*) . (1*) . (\x -> x)) []
= ((5*) . (4*) . (3*) . (2*) . (1*) . (\x -> x)) 100
= ((5*) . (4*) . (3*) . (2*) . (1*)) 100
= ((5*) . (4*) . (3*) . (2*)) 100
= ((5*) . (4*) . (3*)) 200
= ((5*) . (4*)) 600
= (5*) 2400
= 12000

Note that (x*) is the function "multiply by x", i.e. \y -> x*y, while the operator . is function composition. So the composition chain (5*) . (4*) . ... . (1*) is the function "multiply the input by 1, then by 2, then by 3, ..., then by 5".

Your code is written in the so-called continuation-passing-style (CPS), where instead of starting with the initial value (100) and applying functions to it, we perform (tail-) recursive calls and "append" some function to the current "continuation" k (using (x*) . k in your code). Doing so builds a long chain of composed functions and only at the very end we apply that chain to the initial value (100). This code style is not particularly easy to read, in general.

Answer 2

This is multiplication. Indeed this works with the (*) :: Num a => a -> a -> a. It uses the section of an infix operator [Haskell-wiki].

This thus means that (x *) has as type Num a => a -> a with a the type of the variable x, and it will thus multiply a given value by x.

Answer 3

That's an operator section. (x*) is equivalent to \y -> (x * y), a function that multiplies its argument by x.

You can use an operator section with any operator, not just *. This includes ordinary functions enclosed in backticks. For example, all of the following are equivalent:

• (3 `elem`)
• (elem 3)
• \xs -> 3 `elem` xs
• \xs -> elem 3 ex

Answer 4

This is not some kind of special asterisk notation, it's just the standard multiplication operator.

Prelude> 5*7
35

Like any infix operator, you can use sections of the operator:

Prelude> (5*) 7
35
Prelude> (*7) 5
35

To make it clearer what's happening, example with a non-commutative operator:

Prelude> 15 / 3
5.0
Prelude> (15/) 3
5.0
Prelude> (/3) 15
5.0

The point of a section is that you get a function corresponding to taking the second operand while keeping the already-provided one fixed, like

Prelude> map (/3) [21, 30, 45]
[7.0,10.0,15.0]
Prelude> map (24/) [3,4]
[8.0,6.0]

If x has the type, for example, Int, then (x*) has type Int -> Int. Such a function can be composed with another function that gives an Int as the result using the . operator, for example

Prelude> ((4*) . length) "bla"
12       -- same as
Prelude> 4 * length "bla"
12

Such a composed function can not just be applied right away to an argument, it can also be mapped over a list (or generally passed as the argument of a higher-order function):

Prelude> map ((4*) . length) ["bla", "blub"]
[12,16]

In your example, the g is such a higher-order function:

g :: (Int -> Int) -> [Int] -> Int

It takes a function as the first argument, which in the call g (\x -> x) [1..5] is simply the identity function (aka g id [1..5]).

But in the recursive call, g “modifies” that function be successively post-composing it with a multiplication section. For example,

g id [2] ≡ g ((2*) . id) []
         ≡ ((2*) . id) 100
         ≡ (2*) 100
         ≡ 2 * 100
         ≡ 200

With a longer list, it would be

g id [7,8] ≡ g ((7*) . id) [8]
           ≡ g ((8*) . ((7*) . id)) []
           ≡ ((8*) . ((7*) . id)) 100
           ≡ 8 * 7 * id 100
           ≡ 5600