Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to discover the precedence and associativity of a function in GHCI?

Is there an fast and easy way to discover the precedence and associativity a function in GHCI?

I've found that one straightforward method is to bruteforce combining one operator with another other until you get a precedence parsing error (PPE). For example, to discover the precedence/associativity of !!, we can define 10 different operators of infix n for 0 ≤ n < 10:

>>> let infix 0 %; (%) = ($)
>>> undefined % undefined !! undefined
*** Exception: Prelude.undefined
>>> let infix 1 %; (%) = ($)
>>> undefined % undefined !! undefined
*** Exception: Prelude.undefined
[...]
>>> let infix 8 %; (%) = ($)
>>> undefined % undefined !! undefined
*** Exception: Prelude.undefined
>>> let infix 9 %; (%) = ($)
>>> undefined % undefined !! undefined

<interactive>:21:1:
    Precedence parsing error
        cannot mix `%' [infix 9] and `!!' [infixl 9] in the same infix expression

The error tells you what the predences and fixities are. Since the 10 functions defined are non-associative, there's no chance of avoiding a PPE when the precedence levels are equal. The naïve approach would have been to try 10 functions of each associativity, giving a WCET of 20 (because if you start on the same associativity as the target, the 10 with that associativity would pass, but then the failure would happen once you get to the kth precedence of the next associativity, where k is the precedence of the target function).

But is there a faster way? I think you can do bisection to achieve log(10) steps on average. For example, if the target was !!! which is defined as !!, but with infixl 6, we could make an expression (:[]) % "AB" !!! 1, where % is one of the same 10 dummy functions. If the precedence of % is too low to cause a PPE, the expression will yield "B" (because the expression will parse to (:[]) % ("AB" !!! 1)), while if the precedence is too high, it will yield (because the expression will parse to ((:[]) % "AB") !!! 1). Example:

>>> let infixl 6 !!!; (!!!) = (!!)
>>> let infix 5 %; (%) = ($)
>>> (:[]) % "AB" !!! 1
"B"
>>> --too low
>>> let infix 7 %; (%) = ($)
>>> (:[]) % "AB" !!! 1
"*** Exception: Prelude.(!!): index too large

>>> --too high
>>> let infix 6 %; (%) = ($)
>>> (:[]) % "AB" !!! 1

<interactive>:10:1:
    Precedence parsing error
        cannot mix `%' [infix 6] and `!!!' [infixl 6] in the same infix expression
>>> --got it

However, I'm not sure about this approach.

  • You have to maintain the mental state of which number to guess next, and do the division etc in your head (by paper/calculator would probably be slower than just doing the 10 steps in the straightforward method)
  • Is it fully general? Can you always construct a test expression like this?
  • I'm not sure if I can always come up with an expression like this faster than I can just do the straightforward method. In this case it was indeed faster, and I actually came up with the bisection method before I came up with the straightforward method
  • If the previous concern holds valid, does there exist a fully general way to automatically generate expressions of this kind?

Is anyone aware of an alternative method? I can imagine there might be a way to just do this in a single step. But after an hour, the best I could come up with is this bisection method.

like image 835
Dog Avatar asked May 10 '14 21:05

Dog


1 Answers

Yes. You can use the :info command.

Prelude> :info (+)
class Num a where
  (+) :: a -> a -> a
  ...
        -- Defined in `GHC.Num'
infixl 6 +

Prelude> :info (.)
(.) :: (b -> c) -> (a -> b) -> a -> c   -- Defined in `GHC.Base'
infixr 9 .

Prelude> :info ($)
($) :: (a -> b) -> a -> b       -- Defined in `GHC.Base'
infixr 0 $

If it doesn't say, it's the default of infixl 9.

like image 52
kqr Avatar answered Nov 05 '22 21:11

kqr