Permutations of a list in Haskell
3. Monadic notation

Let's start with your last question, as it has a clichéd answer: Do whatever you prefer.  I often find the bind operator &gt;&gt;= nicer to read, but switch to do-notation as soon as the code gets complicated.  Another rule of thumb is to use do-notation if the code is easier to express imperatively.  Both notations are equivalent, there is no performance impact.

1. Idiomatic Haskell

Haskell has a few conventions about variable naming.  Lists are commonly referred to as xs or ys (think plural of x), while function parameters are named f or g.  Type parameters are almost always taken from the first letters of the alphabet.

perms3 :: (a -&gt; a -&gt; b) -&gt; [a] -&gt; [b] 
perms3  f xs               = perms3' f xs xs
perms3' _ []         _     = []
perms3' c (x:xs)    [y]    = f y z : perms3' f xs  xs
perms3' c xs'@(x:_) (y:ys) = f x y : perms3' f xs' ys


Since perms3' is only used within perms3, it would make sense to define it as a local function.  This has the additional benefit that we can drop f from its parameter list, since it's already in scope and won't change.

perms3 :: (a -&gt; a -&gt; b) -&gt; [a] -&gt; [b] 
perms3  f xs = perms3' xs xs
  where
    perms3' []         _     = []
    perms3' (x:xs)    [y]    = f y z:perms3' f xs  xs
    perms3' xs'@(x:_) (y:ys) = f x y:perms3' f xs' ys


2. Performance improvement

Pattern matching on lists usually takes two cases: empty and non-empty lists.  This can reduce code (DRY etc) and actually improve performance, as tests for empty lists are faster than tests for singleton lists.

perms4 :: (a -&gt; a -&gt; b) -&gt; [a] -&gt; [b] 
perms4  f xs = perms4' xs xs
  where
    perms4' []        _      = []
    perms4' (_:ys)    []     = perms4' ys ys
    perms4' ys'@(y:_) (z:zs) = f y z : perms4' ys' zs


A quick test gave me a 20% improvement compared to perms3.

Notes on perms2

The fold in perms2 is just a map.  Using partial application, it could be written as

perms5 _ [] = []
perms5 f xs'@(x:xs) = map (f x) xs' ++ perms5 f xs
-- faster:
-- perms5 f xs'@(x:xs) = foldr ((:) . f x) [] xs' ++ perms5 f xs


However, this is (somewhat surprisingly) slower than the fold.  AFAICT, this is due to the fact that ghc won't inline map, but will do so with foldr.

Finally, here is how I (naïvely) would have written the code.  Looks nice,  performs terribly.

import Data.List (concatMap, tails)
perms6 f = concatMap pairs . tails
  where
    pairs [] = []
    pairs (ys'@(y:_)) = map (f y) ys'


or

perms7 f xs = concat $ zipWith (map . f) xs (tails xs)