Defining the associativity of a custom operator in Haskell

Admin 1
Viewed 187

I'm playing around with custom operators, infix, infixl and infixr. Now I'm confused.

I've written a custom operator for list-multiplication, and thought, that declaring it as a simple infix-operator with no directional associativity, would automatically provide both cases, nr * list and list * number, as they can be interchanged at will.

import Prelude hiding ((*))

infix 6 *

(*) :: Int -> [a] -> [a]
n * l = if n < 0 then [] 
                 else l ++ (n - 1) * l

Now, 3 * [1, 2, 3] returns [1, 2, 3, 1, 2, 3, 1, 2, 3] as expected, but [1, 2, 3] * 3 throws an error, because I never explicitly defined list * nr.

My question: What is the unique functionality of infix and why not allways use infixl or infixr instead, as it should make no difference?

I understand "no directional associativity" / infix as a synonym to "is commutative":

a + b + c has no directional associativity and is commutative and can be written as (a + b) + c, a + (b + c), b + a + c, (b + a) + c, and so on...

For my example 2 * [1, 2] * 1 is the same as 1 * (2 * [1, 2]), and all other combinations of that, so i dont really get, why there is no implicit reshaping for commutative operator declarations, even with different typed operands.

infix-operator operators haskell
1 Answers

The fixity declarations only affect parsing, not the definitions of the operators.

If you use infixl, then a * b * c is parsed as (a * b) * c.

If you use infixr, then a * b * c is parsed as a * (b * c).

If you use infix, then you are saying that a * b * c cannot be parsed; you must use parentheses to specify whether you mean (a * b) * c or a * (b * c). Compare

Prelude> infix 6 ***; (***) = (+)
Prelude> 1 *** 2 *** 3

<interactive>:8:1: error:
    Precedence parsing error
        cannot mix ‘***’ [infix 6] and ‘***’ [infix 6] in the same infix expression
Prelude> infixl 6 ***; (***) = (+)
Prelude> 1 *** 2 *** 3
6

In your case, * is not fully associative, because the types don't line up. It can be right-associative, because 3 * (6 * []) typechecks but not left-associative because (3 * 6) * [] does not. Using infix, you disallow 3 * 6 * []. If you used infixr, then you could write that and the parser will treat it as 3 * (6 * []).

Making an operator like this commutative is tricky, because at the type level they are two different operators. That's easy enough to define:

-- Ignoring the fact that both of these operators are already
-- used by the Applicative class for different purposes.

(*>) :: Int -> [a] -> [a]
0 *> l = []
n *> l = l ++ (n-1) * l

(<*) :: [a] -> Int -> [a]
(<*) = flip (*>)

Making * work as both Int -> [a] -> [a] and [a] -> Int -> [a] is tricky, if not impossible. (Maybe something involving a multi-parameter type family?

-- Compiles, but does not run. Not sure why...
{-# LANGUAGE TypeFamilies, MultiParamTypeClasses, FlexibleContexts #-}

class Multiplable x y where
  type Result x y
  (***) :: x -> y -> Result x y

instance Multiplable Int [a] where
   type Result Int [a] = [a]
   0 *** l = []
   n *** l = l ++ ((n - 1) *** l)

instance Multiplable [a] Int where
  type Result [a] Int = [a]
  l *** 0 = []
  l *** n = l ++ (l *** (n - 1))

)

Your understanding of associativity and commutativity is incorrect. "Not associative" is not a synonym for "commutative". In fact, the two properties are orthogonal: a given operator can be both, or neither, or only one of the two.

  • Integer addition is associative and commutative.

  • Integer subtraction is neither associative nor commutative.

  • Matrix multiplication is associative, but not commutative. (BA can be different from AB or even undefined altogether.)

  • The NAND operation (the negation of logical AND) is commutative, but not associative:

    (True NAND True) NAND False == False NAND False == True
True NAND (True NAND False) == True NAND True == False
user_11268410
Related