Free Sections

Haskell Syntax Extension

by Andrew Seniuk

  f :: Int -> Bool -> Char -> Float -> String
  f 4 True         -- Char -> Float -> String

Philosophically, use of this sort of syntax promotes "higher-order programming", since any expression can so easily be made into a function, in numerous ways, simply by replacing parts of it with freesect wildcards. That this is worthwhile is demonstrated by the frequent usefulness of sections.

Some examples, including illustrations of context inferencing:

• _[ __ ]_ <=> ( __ ) <=> id
• map  _[ (+) __ 2 ]_  [1,2,3]   =>   [3,4,5]
• map   ( (+) __ 2 )   [1,2,3]   =>   [3,4,5]
• zipWith $ f __ $ g __ z       <=>   zipWith _[ f __ $ g __ z ]_

For a more complex example, consider a situation where some API provides you with the dreaded dreadme function, which you have need of using. The example is designed to show that you can really put the __'s anywhere on a RHS that an expression can go.

  {-# LANGUAGE FreeSections #-}  -- use "{- #" if compiling with ghc -F

  tableA = [ [1,2,3], [4,5], [6,7,8,9] ]
  tableB = [ [9,8,7], [6,5], [4,3,2,1] ]

  data D a = D Int [a]

  v = map3  _[ dreadme tableA __ (repeat True,__) (D __ [(+),(*)]) ]_
            [tableA,tableB]
            [0..]
            [-1,1]

  v = map3  (\ fs0 fs1 fs2 -> dreadme tableA fs0 (repeat True,fs1) (D fs2 [(+),(*)]) )
            [tableA,tableB]
            [0..]
            [-1,1]

  dreadme :: [[Int]] -> [[Int]] -> ([Bool],Int) -> D (Int->Int->Int) -> String
  dreadme tabA tabB (ps,q) (D wt flst)
    = show $ map (!!q) $ map2 f tabA tabB
    where f rowA rowB =   map2 (<) (repeat rowA)
                        $ map2' (filter' ps flst) rowB (map ((q+).(wt*)) rowB)
(base cases)
  filter' :: [Bool] -> [a] -> [a]
  filter' (p:ps) (x:xs) = if p then x:filter' ps xs
                               else   filter' ps xs
  map2 :: (a->b->c) -> [a] -> [b] -> [c]
  map2 f (x:xs) (y:ys) = (f x y) : map2 f xs ys
  map2' :: [a->a->a] -> [a] -> [a] -> [[a]]
  map2' (f:fs) xs ys = (map2 f xs ys) : map2' fs xs ys
  map3 :: (a->b->c->d) -> [a] -> [b] -> [c] -> [d]
  map3 f (x:xs) (y:ys) (z:zs) = (f x y z) : map3 f xs ys zs
  filter' :: [Bool] -> [a] -> [a]
  filter' (p:ps) (x:xs) = if p then x:filter' ps xs
                               else   filter' ps xs
  map2 :: (a->b->c) -> [a] -> [b] -> [c]
  map2 f _ [] = []
  map2 f [] _ = []
  map2 f (x:xs) (y:ys) = (f x y) : map2 f xs ys
  map2' :: [a->a->a] -> [a] -> [a] -> [[a]]
  map2' [] _ _ = []
  map2' _ [] _ = []
  map2' _ _ [] = []
  map2' (f:fs) xs ys = (map2 f xs ys) : map2' fs xs ys
  map3 :: (a->b->c->d) -> [a] -> [b] -> [c] -> [d]
  map3 f _ _ [] = []
  map3 f _ [] _ = []
  map3 f [] _ _ = []
  map3 f (x:xs) (y:ys) (z:zs) = (f x y z) : map3 f xs ys zs
  main = print v

Some virtues of the new syntax

• the lambda forces the programmer to invent names for the wildcards
• the lambda forces the programmer to repeat those names, and place them correctly
• freesect wildcards stand out vividly, indicating where the awaited expressions will go
• reading the lambda requires visual pattern-matching between left and right sides of the lambda
• the lambda is longer overall, and prefaces the expression of interest with something like micro-boilerplate

Implementation

Default context inferencing

Background

  <dolio> map (foo (g _) x) (h _)
  <dolio> Matter of fact, what does "map (foo (g _) x) (h _)" mean?

  (map (foo (g _) x) (h _))  =>  \ y z -> map (foo (g y) x) (h z)

  (map $ (foo (g __) x) (h __))  =>  map ( \ y z -> (foo (g y) x) (h z) )

       map  _[foo (g __) x]_   _[h __]_
  <=>  map   (foo (g __) x)    _[h __]_
  <=>  map  _[foo (g __) x]_    (h __)
  <=> (map  _[foo (g __) x]_  $  h __)

  map (\y->foo (g y) x) (\z->h z)

Other details

Fresh identifiers generated by FreeSect are guaranteed to be unique among names referenced within a module. There is no danger of exporting these names inadvertently, as they never have top-level scope. Imported names which are in scope but never used will not incur conflicts.

A few things don't work quite right yet. Guarded RHS's are not yet handled. Default free section contexts in let expressions need to be parenthesised. Work continues...

How to run it

Feedback