Haskell permutations matching criteria
The findIndex seems un-Haskelly and the fmap on the result of findIndex feels just wrong. 


There's nothing wrong with fmap.

One thing I would advise is replacing (\x -&gt; x - 1) with (minus 1). Also, [ls | ls &lt;- lss, p ls] is probably best rewritten to use filter. 

If you format your code more nicely, I think you'd find it reasonably appealing:

g = findIndex . (==)

p l r ls = g l ls &lt;= g r ls

sLeftOf l r lss = filter (p l r) lss

sDirectLeftOf l r lss = filter (p l r) $ fmap (minus 1) (g ls)



  The first leftOf is immediately to left of and the second is somewhere to the left of; but this won't work for a single list.


Seems like a fairly contrived solution. elem and zip are still \$O(n)\$ so I don't think this accomplishes what you intended. If you're concerned about performance, I'd suggest using a keyed map so that lookups become \$O(\log n)\$ - searching an array will be \$O(n)\$ just like searching a list.

Also, you define

leftOf' x xs y ys = guard $ (x,y) `elem` (aux xs (tail ys))
aux a b@(_:ys) = (zip a b) ++ aux a ys
aux _ []       = []


which is not used anywhere. Passing the -Wall option to GHC will warn you any time you do something like this.