text:
Tips for golfing in Haskell
What general tips do you have for golfing in Haskell? I am looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to Haskell. Please post only one tip per answer.

If you are new to golfing in Haskell, please have a look at the Guide to Golfing Rules in Haskell. There is also a dedicated Haskell chat room: Of Monads and Men.

Seeing the number of answers till now, I am in doubt about whether Haskell is even a good language for code golfing or not?

Why only one tip per answer? Also, every language is a good language for golfing. Just don't always expect to win.

@unclemeat This way people could upvote the good ones to the top without upvoting the bad ones only because they were written by the same guy in the same answer.

Special request, String compression.

This is probably not suited as an anwer, but I'm still want to add it here: https://wiki.haskell.org/Prime_numbers_miscellaneous#One-liners

Another (rather funny, but still interesting) one: http://www.willamette.edu/~fruehr/haskell/evolution.html

Also another link: https://wiki.haskell.org/Blow_your_mind

Define infix operators instead of binary functions
This saves usually one or two spaces per definition or call.
0!(y:_)=y
x!(y:z)=(x-1)!z

vs.
f 0(y:_)=y
f x(y:z)=f(x-1)z

The available symbols for 1-byte operators are !, #, %, &, and ?. All other ASCII punctuation is either already defined as an operator by the Prelude (such as $) or has a special meaning in Haskell's syntax (such as @).
If you need more than five operators, you could use combinations of the above, such as !#, or certain Unicode punctuation characters, such as these (all 2 bytes in UTF-8):
¡ ¢ £ ¤ ¥ ¦ § ¨ © ¬ ® ¯ ° ± ´ ¶ · ¸ ¿ × ÷

Note: this can also be used for functions with three or more arguments. (x!y)z=x+y*z and (x#y)z u=x*z+y*u both work as expected.

This can also be used for function arguments, e.g. \f g(!)x y->f g!x y instead of \f g j x y->j(f g)(x y)

Sometimes it's beneficial to change unary functions to binary operators if you'd otherwise have to use parentheses - g x=…;g(f x) is longer than _?x=…;0!f x

Use pointless (or -free) notation where appropriate
Often a function with one or two parameters can be written point free.
So a lookup for a list of tuples whose elements are swapped is naïvely written as:
revlookup :: Eq b => b -> [(a, b)] -> Maybe a
revlookup e l=lookup e(map swap l)

(the type is there just to help you understand what it's doing.)
for our purposes this is much better:
revlookup=(.map swap).lookup

Use guards not conditionals:
f a=if a>0 then 3 else 7
g a|a>0=3|True=7

Use semicolons not indents
f a=do
  this
  that
g a=do this;that

Use boolean expressions for boolean functions
f a=if zzz then True else f yyy
g a=zzz||f yyy

(SO is being a pain about letting me post these separately)

also, use multiple guards instead of && when inside a list comprehension.

Good one Jan - you should make that into an answer, I'll vote for it

The first example can be further shortened by True => 1>0

in the first example, I assume you mean f a=if a>0 then 3 else 7

Guard even works if there's no argument in it.

6<9 > 1>0 change my mind

Use the list monad
A quick review:
xs >> ys        =  concat $ replicate (length xs) ys
xs >>= f        =  concatMap f xs
mapM id[a,b,c]  =  cartesian product of lists: a × b × c
mapM f[a,b,c]   =  cartesian product of lists: f a × f b × f c

Examples:

Repeating a list twice
Prelude> "aa">>[1..5]
[1,2,3,4,5,1,2,3,4,5]

Shorter concatMap
Prelude> reverse=<<["Abc","Defgh","Ijkl"]
"cbAhgfeDlkjI"

Shorter concat + list comprehension
Prelude> do x<-[1..5];[1..x]
[1,1,2,1,2,3,1,2,3,4,1,2,3,4,5]

Cartesian product
Prelude> mapM id["Hh","io",".!"]
["Hi.","Hi!","Ho.","Ho!","hi.","hi!","ho.","ho!"]

List of coordinates on a lattice
Prelude> mapM(\x->[0..x])[3,2]
[[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2],[3,0],[3,1],[3,2]]

Annother use I found useful is [0..b]>>[a] instead of replicate a b.

@WheatWizard a<$[1..b] is even shorter, for replicate.

Using =<< forces you to import Control.Monad. If you don't need that for some other reason, swapping the arguments and using >>= seems more concise.

OTOH, if you need Data.Traversable anyway, the Cartesian product example can be shortened to for["Hh","io",".!"]id.

(=<<) is in Prelude, actually! I've used it a lot.

An alternative to mapM id for the cartesian product is sequence :: (Monad m, Traversable t) => t (m a) -> m (t a) but it is one byte longer, but can be handy if you have to pass it to some other function.

Use GHC 7.10
The first version of GHC that contained this stuff was released on March 27, 2015.
It's the latest version, and Prelude got some new additions that are useful for golfing:
The (<$>) and (<*>) operators
These useful operators from Data.Applicative made it in! <$> is just fmap, so you can replace map f x and fmap f x with f<$>x everywhere and win back bytes. Also, <*> is useful in the Applicative instance for lists:
Prelude> (,)<$>[1..2]<*>"abcd"
[(1,'a'),(1,'b'),(1,'c'),(1,'d'),(2,'a'),(2,'b'),(2,'c'),(2,'d')]

The (<$) operator
x<$a is equivalent to fmap (const x) a; i.e. replace every element in a container by x.
This is often a nice alternative to replicate: 4<$[1..n] is shorter than replicate n 4.
The Foldable/Traversable Proposal
The following functions got lifted from working on lists [a] to general Foldable types t a:
fold*, null, length, elem, maximum, minimum, sum, product
and, or, any, all, concat, concatMap

This means they now also work on Maybe a, where they behave just like "lists with at most one element". For example, null Nothing == True, or sum (Just 3) == 3. Similarly, length returns 0 for Nothing and 1 for Just values. Instead of writing x==Just y you can write elem y x.
You can also apply them on tuples, which works as if you'd called \(a, b) -> [b] first. It's almost completely useless, but or :: (a, Bool) -> Bool is one character shorter than snd, and elem b is shorter than (==b).snd.
The Monoid functions mempty and mappend
Not often a life-saver, but if you can infer the type, mempty is one byte shorter than Nothing, so there's that.

+1 It's great to hear about '<$>and<*>` making it into Prelude! That should be usefull even when It's not code golf (applicative is such a long word).

Warning about flat replacement: if your language version is newer than the challenge, your solution is inegligible for winning. If you want to update your existing answers or answer, don't overwrite your existing solution. Write an appendix.

Funny there is [1..2] in there. that's just [1,2]

In the same version we also got <* from Applicative, which for lists is xs <* ys == concatMap (replicate (length ys)) xs. This is different from xs >> ys or xs *> ys which is concat (replicate (length ys)) xs. pure which is a shorter return came at this point too.

You can now use <> instead of mappend, it's now (with GHC 8.4.1) part of the Prelude.

@BMO I used <> to successfully beat the old quine (with the function instance, which H.PWiz then improved with the IO instance), so it is definitely worth mentioning.

Occasionally you can use fail"" instead of Nothing.

Now I know why FTP was finally accepted.

Use 1<2 instead of True and 1>2 instead of False.
g x|x<10=10|True=x
f x|x<10=10|1<2=x

This isn't really specific to Haskell: it's applicable to just about every language which has a Boolean type as opposed to truthy and falsy values of other types.

Can anyone explain this?

this isn't a good example, i would just golf this as f=max 10.

@MasterMastic this is just writing if(true) in other languages. in the prelude, otherwise is actually the boolean value True.

@PeterTaylor I think this is still valuable for new haskellians (like me) as I first learned to use otherwise.

interact :: (String → String) → IO ()
People often forget that this function exists - it grabs all of stdin and applies it to a (pure) function. I often see main-code along the lines of
main=getContents>>=print.foo

while
main=interact$show.foo

is quite a bit shorter. It is in the Prelude so no need for imports!

Use list comprehensions (in clever ways)
Everyone knows they're useful syntax, often shorter than map + a lambda:
Prelude> [[1..x]>>show x|x<-[1..9]]
["1","22","333","4444","55555","666666","7777777","88888888","999999999"]

Or filter (and optionally a map at the same time):
Prelude> [show x|x<-[1..60],mod 60x<1]
["1","2","3","4","5","6","10","12","15","20","30","60"]

But there are some weirder uses that come in handy now and then. For one, a list comprehension doesn't need to contain any <- arrows at all:
Prelude> [1|False]
[]
Prelude> [1|True]
[1]

Which means instead of if p then[x]else[], you can write [x|p]. Also, to count the number of elements of a list satisfying a condition, intuitively you would write:
length$filter p x

But this is shorter:
sum[1|y<-x,p y]

I actually used all of these before, but I didn't think to put them here.

Match a constant value
A list comprehension can pattern match on a constant.

[0|0<-l]

This extracts the 0's of a list l, i.e. makes a list of as many 0's as are in l.

[1|[]<-f<$>l]

This makes a list of as many 1's as there are elements of l that f takes to the empty list (using <$> as infix map). Apply sum to count these elements.
Compare:
[1|[]<-f<$>l]
[1|x<-l,f x==[]]

[x|(0,x)<-l]

A constant can be used as part of a pattern match. This extracts the second entries of all tuples whose first entry is 0.

Note that all of these require an actual constant literal, not a the value of a variable. For example, let x=1 in [1|x<-[1,2,3]] will output [1,1,1], not [1], because the outer x binding is overwritten.

Know your Prelude
Fire up GHCi and scroll through the Prelude documentation. Whenever you cross a function that has a short name, it can pay off to look for some cases where it might be useful.
For example, suppose you wish to transform a string s = "abc\ndef\nghi" into one that's space-separated, "abc def ghi". The obvious way is:
unwords$lines s

But you can do better if you abuse max, and the fact that \n < space < printable ASCII:
max ' '<$>s

Another example is lex :: String -> [(String, String)], which does something quite mysterious:
Prelude> lex "   some string of Haskell tokens  123  "
[("some"," string of Haskell tokens  123  ")]

Try fst=<<lex s to get the first token from a string, skipping whitespace. Here is a clever solution by henkma that uses lex.show on Rational values.

lookup is another useful prelude function

Arguments can be shorter than definitions
I just got outgolfed in a very curious way by henkma.
If an auxiliary function f in your answer uses an operator that isn’t used elsewhere in your answer, and f is called once, make the operator an argument of f.
This:
(!)=take
f a=5!a++3!a
reverse.f

Is two bytes longer than this:
f(!)a=5!a++3!a
reverse.f take

Use words instead of a long list of strings. This isn't really specific to Haskell, other languages have similar tricks too.
["foo","bar"]
words"foo bar"  -- 1 byte longer

["foo","bar","baz"]
words"foo bar baz"  -- 1 byte shorter

["foo","bar","baz","qux"]
words"foo bar baz qux"    -- 3 bytes shorter

Shorter conditional
last$x:[y|b]

is equivalent to
if b then y else x

Here's how it works:
             [y|b]   x:[y|b]   last$x:[y|b]
if...      +--------------------------------
b == False | []      [x]       x
b == True  | [y]     [x,y]     y

Wouldnt using bool be shorter as you don't need a list  comprehension

@Potato44 That's in Data.Bool, which costs bytes to import.

Know your monadic functions
1)simulate monadic functions using mapM.
a lot of times code will have sequence(map f xs), but it can be replaced with mapM f xs. even when just using sequence alone it is longer then mapM id.
2)combine functions using (>>=) (or (=<<))
the function monad version of (>>=) is defined as so:
(f >>= g) x = g (f x) x

it can be useful for creating functions which can't be expressed as a pipeline. for example, \x->x==nub x is longer than nub>>=(==), and \t->zip(tail t)t is longer than tail>>=zip.

+1 -- I hadn't even realised that there was a monad instance for functions.  that could be very handy :)

Side note: Though it's part of Applicative and not Monad there's the implementation for pure as well which is shorter than const and actually helped me before.

Shorter conditionals when one outcome is the empty list
When you need a conditional which returns the list A or the empty list [] depending on some condition C, then there exist some shorter alternatives to the usual conditional constructs:
if(C)then(A)else[] -- the normal conditional
last$[]:[A|C]      -- the golfy all-round-conditional
concat[A|C]        -- shorter and works when surrounded by infix operator
id=<<[A|C]         -- even shorter but might conflict with other infix operators
[x|C,x<-A]         -- same length and no-conflict-guarantee™
[0|C]>>A           -- shortest way, but needs surrounding parenthesis more often than not
do[0|C];A          -- longer but works in some places where the above would need parents

Examples: 1, 2

The second one has A and [] switched.

@ØrjanJohansen Corrected, thanks!

Aha! But *> has higher fixity than >> (still a bit low for comfort.)

do[0|C];A could sometimes be useful. i.e X++do[0|C];A

@H.PWiz Good one, I added it to the list

Don't waste the "otherwise" guard
A final guard that's a catch-all True (shorter as 1>0) can be used to bind a variable. Compare:
... |1>0=1/(x+y)
... |z<-x+y=1/z

... |1>0=sum l-sum m
... |s<-sum=s l-s m

Since the guard is mandatory and is otherwise wasted, little is needed to make this worth it. It's enough to save a pair of parens or bind a length-3 expression that's used twice. Sometimes you can negate guards to make the final case be the expression that best uses a binding.

Don't use backticks too often.
Backticks are a cool tool for making sections of prefix functions, but can sometimes be misused.
Once I saw someone write this subexpression:
(x`v`)

Although it is the same as just v x.
Another example is writing (x+1)`div`y
as opposed to div(x+1)y.
I see it happen around div and elem more often because these functions are usually used as infix in regular code.

Don't you mean making sections of prefix functions?

@Cyoce Yes, of course

Exception: making section of prefix functions are shorter than using flip. So (\elem`"ABC")instead offlip elem"ABC"`

Use the cons operator (:)
when concatenating lists, if the first is of length 1 then use : instead.
a++" "++b
a++' ':b  -- one character shorter

[3]++l
3:l    -- three characters shorter

Worth noting that it's right associative, so you can keep using it for any number of single items at the beginning of the list, e.g. 1:2:3:x rather than [1,2,3]++x.

Use pattern guards
They're shorter than a let or a lambda that deconstructs the arguments of a function you're defining. This helps when you need something like fromJust from Data.Maybe:
f x=let Just c=… in c

is longer than
f x=(\(Just c)->c)$…

is longer than
m(Just c)=c;f x=m$…

is longer than
f x|Just c<-…=c

In fact, they’re shorter even when binding a plain old value instead of deconstructing: see xnor’s tip.

Well, the lambda one doesn't need the dollar sign, and it seems this change makes the lengths of this and the next snippet the same

I'm assuming e isn't actually one token but a longer expression that needs $ before it, which is usually the case.

Use GHC 8.4.1 (or later)
With the Semigroup Monoid Proposal and the release of GHC 8.4.1, Semigroup has been moved to the Prelude. This gives us:
(<>) :: Semigroup a => a -> a -> a

Now these might seem useless at first glance, but looking closer we notice that Monoid a => (x -> a) is an instance of Monoid1, in which case we have the implementation:
(f <> g) xs = f xs <> g xs

This can be quite useful with for example lists, knowing that (<>) is the same as (++) for lists. So we have for example:
(init <> reverse) [1,2,3] ≡ init [1,2,3] <> reverse [1,2,3]
                          ≡ [1,2] <> [3,2,1]
                          ≡ [1,2] ++ [3,2,1]
                          ≡ [1,2,3,2,1]

However, this is not the only useful case: Knowing that [x] -> [x] is an instance of Monoid, we also have a -> [x] -> [x] an instance of Monoid (you can iterate this as many times as you want):
(drop <> take) 2 [1,2,3,4,5] ≡ (drop 2 <> take 2) [1,2,3,4,5]
                             ≡ drop 2 [1,2,3,4,5] <> take 2 [1,2,3,4,5]
                             ≡ [3,4,5] <> [1,2]
                             ≡ [3,4,5,1,2]

1: Note that Monoid a \$\implies\$ Semigroup a.
Overview what we gained so far
Using this trick we have these (not exhaustive) helpers, note that we can chain them:
duplicate    = id <> id
triple²      = id <> id <> id
palindromize = init <> reverse
rotateLeft   = drop <> take
removeElementAt = take <> drop . succ
removeNElementsAt n = take <> drop . (+n)

2: This could also be ([1..3]>>) for the same bytecount be shorter (see comment by Ørjan Johansen).
Where are the \$(\mathbb{Z},\texttt{+})\$ and \$(\mathbb{Z},\texttt{*})\$ monoids?
If we want to use the \$(\mathbb{Z},\texttt{+})\$ monoid, we need to tell GHC that. It can not decide for us which one it should use, therefore there are two newtypes which allow this - Sum and Product.
Given that the consensus is to allow implicitly typed functions, we are probably allowed to do so if the challenge does not talk about a specific implementation for integers. Using this we can for example write \$n\$th oblong number as
id<>(+1)

which is shorter than f n=n*(n-1) or even (*)=<<succ/(*)<*>succ.
Try it online!3
3: Note that we need to use (+1) and cannot use succ since GHC can't know that there is an instance of Enum.
Other noteworthy related tricks
Instances that might be useful not covered above:
()
Ordering
(Monoid a, Monoid b) => Monoid (a,b)  -- (also 3-,4- and 5-tuples)
Monoid a => Monoid (IO a)
Ord k => Monoid (Map k v)             -- from Data.Map

It might be worth noting that there is mconcat too:
mconcat [f1,f2,…,fN] ≡ f1 <> f2 <> … <> fN

This will probably not be useful often, for it needs at least \$3-11\$ functions (depending on the need of parentheses, see comments), but it might be in case you have some list Monoid a => [a] already.

Furthermore mempty can be useful since it is shorter than Nothing or even pure Nothing, ([],[]) etc.

Another useful instance is Monoid a => Monoid (IO a) which has successfully been used for the currently shortest quine as
(putStr <> print) "foo" ≡ putStr "foo" <> print "foo"
                        ≡ do x <- putStr "foo"
                             y <- print "foo"
                             pure $ x <> y
                        ≡ do putStr "foo"
                             print "foo"
                             pure ()
                        ≡ putStr "foo" >> print "foo"

("123">>) is shorter.

@ØrjanJohansen: Ah damn, it was meant for educational purposes :P (showing that you can join multiple functions, not only two)

By my count 8−11 functions should be 4−11. (Best case if all functions need parentheses with <>.)

@ØrjanJohansen: That's how I counted (ie. not assuming anything about the fs, but I should probably have written 9-11 or 8-10 to keep it consistent. I adjusted it to 4-11 (sounds better, though it's still a lot).

Oh, I thought of parentheses around each individual function, but I did not consider parentheses around the whole. In that case it can beat it with 3: mconcat[f1,f2,f3] is a byte shorter than ((f1)<>(f2)<>(f3)).

@ØrjanJohansen: If someone actually needs all these parens, maybe they should switch to LISP ^^ Seriously though, a lot of times the outer parentheses are needed, unfortunately. And it's a fair point with the inner parentheses, with the list one does not need to shy away from using ($).

I think you meant Monoid a => Monoid (IO a). The second Monoid is missing.

@dfeuer: Yes, you're right that was a typo. Fixed it, thank you for carefully reading through it :)

Shorter syntax for local declarations
Sometimes you need to define a local function or operator, but it costs lots of bytes to write where or let…in or to lift it to top-level by adding extra arguments.
g~(a:b)=2!g b where k!l=k:take(a-1)l++(k+1)!drop(a-1)l
g~(a:b)=let k!l=k:take(a-1)l++(k+1)!drop(a-1)l in 2!g b
g~(a:b)=2!g b$a;(k!l)a=k:take(a-1)l++((k+1)!drop(a-1)l)a

Fortunately, Haskell has a confusing and seldom-used but reasonably terse syntax for local declarations:
fun1 pattern1 | let fun2 pattern2 = expr2 = expr1

In this case:
g~(a:b)|let k!l=k:take(a-1)l++(k+1)!drop(a-1)l=2!g b

You can use this syntax with multi-statement declarations or multiple declarations, and it even nests:
fun1 pattern1 | let fun2 pattern2 = expr2; fun2 pattern2' = expr2' = expr1
fun1 pattern1 | let fun2 pattern2 = expr2; fun3 pattern3 = expr3 = expr1
fun1 pattern1 | let fun2 pattern2 | let fun3 pattern3 = expr3 = expr2 = expr1

It also works for binding variables or other patterns, though pattern guards tend to be shorter for that unless you’re also binding functions.

This also works inside list comprehensions: [f 1|let f x=x+1].

Lambda parsing rules
A lambda-expression doesn't actually need parentheses around it - it just rather greedily grabs everything so the whole thing still parses, e.g. until

a closing paren - (foo$ \x -> succ x)
an in - let a = \x -> succ x in a 4
the end of the line - main = getContents>>= \x -> head $ words x
etc..

is encountered, and there are some weird edge-cases where this can save you a byte or two. I believe \ can also be used to define operators, so when exploiting this you will need a space when writing a lambda directly after an operator (like in the third example).
Here is an example of where using a lambda was the shortest thing I could figure out. The code basically looks like:
a%f=...
f t=sortBy(% \c->...)['A'..'Z']

Try rearranging function definitions and/or arguments
You can sometimes save a couple of bytes by changing the order of pattern-matching cases in a function definition.
These savings are cheap, but easy to overlook.
As an example, consider the following earlier version of (a part of) this answer:
(g?x)[]=x
(g?x)(a:b)=g(g?x$b)a

This is a recursive definition of ?, with the base case being the empty list.
Since [] is not a useful value, we should swap the definitions and replace it with the wildcard _ or a dummy argument y, saving a byte:
(g?x)(a:b)=g(g?x$b)a
(g?x)y=x

From the same answer, consider this definition:
f#[]=[]
f#(a:b)=f a:f#b

The empty list occurs in the return value, so we can save two bytes by swapping the cases:
f#(a:b)=f a:f#b
f#x=x

Also, the order of function arguments can sometimes make a difference by allowing you to remove unnecessary whitespace. Consider an earlier version of this answer:
h p q a|a>z=0:h p(q+2)(a-1%q)|1<2=1:h(p+2)q(a+1%p)

There's an annoying piece of whitespace between h and p in the first branch.
We can get rid of it by defining h a p q instead of h p q a:
h a p q|a>z=0:h(a-1%q)p(q+2)|1<2=1:h(a+1%p)(p+2)q

Working with the minus sign
The minus sign - is an annoying exception to many syntax rules.
This tip lists some short ways of expressing negation and subtraction in Haskell.
Please let me know if I've missed something.
Negation

To negate an expression e, just do -e. For example, -length[1,2] gives -2.
If e is even moderately complex, you will need parentheses around e, but you can usually save a byte by moving them around: -length(take 3 x) is shorter than -(length$take 3 x).
If e is preceded by = or an infix operator of fixity less than 6, you need a space: f= -2 defines f and k< -2 tests if k is less than -2. If the fixity is 6 or greater, you need parens: 2^^(-2) gives 0.25. You can usually rearrange stuff to get rid of these: for example, do -k>2 instead of k< -2.
Similarly, if ! is an operator, then -a!b is parsed as (-a)!b if the fixity of ! is at most 6 (so -1<1 gives True), and -(a!b) otherwise (so -[1,2]!!0 gives -1). The default fixity of user-defined operators and backticked functions is 9, so they follow the second rule.
To turn negation into a function (to use with map etc), use the section (0-).

Subtraction

To get a function that subtracts k, use the section (-k+), which adds -k. k can even be a pretty complex expression: (-2*length x+) works as expected.
To subtract 1, use pred instead, unless it would require a space on both sides. This is rare and usually happens with until or a user-defined function, since map pred x can be replaced by pred<$>x and iterate pred x by [x,x-1..]. And if you have f pred x somewhere, you should probably define f as an infix function anyway. See this tip.

Use , instead of && in guards
Multiple conditions in a guard that all have to hold can be combined with , instead of &&.
f a b | a/=5 && b/=7 = ...
f a b | a/=5 ,  b/=7 = ...

It doesn't have to be conditions either, you can do things like this:
f xs m | [x] <- xs, Just y <- m, x > 3 = y

Get suffixes
Use scanr(:)[] to get the suffixes of a list:
λ scanr(:)[] "abc"
["abc","bc","c",""]

This is much shorter than tails after import Data.List. You can do prefixes with scanr(\_->init)=<<id (found by Ørjan Johansen).
λ  scanr(\_->init)=<<id $ "abc"
["","a","ab","abc"]

This saves a byte over
scanl(\s c->s++[c])[]

Perhaps scanl(flip(:))[] "abc" = ["","a","ba","cba"] is also worth mentioning – sometimes the prefixes being backwards doesn't matter.

Ørjan Johansen found a one-byte shorter alternative for prefixes: scanr(\_->init)=<<id

Avoid repeat n
-- 8 bytes, whitespace might be needed before and after
repeat n

-- 8 bytes, whitespace might be needed before
cycle[n]

-- 7 bytes, whitespace might be needed before and after, can be reused,
-- needs an assignment, n needs to be global
l=n:l;l

-- 7 bytes, never needs whitespace, n needs to derive from Enum,
-- n has to be short enough to be repeated twice
[n,n..]

Either of those four expressions will produce an infinite list of n's.
It's a very specific tip but it can save up to 3 bytes!

If n is global, l=n:l;l is the same length and works for (some) longer expressions. (May need whitespace though.)

@ØrjanJohansen I incorporated it into the post. Thanks!

Bind using guards
When defining a named function, you can bind an expression to a variable in a guard. For example,
f s|w<-words s=...

does the same as
f s=let w=words s in ...
f s=(\w->...)$words s

Use this to save on repeated expressions. When the expression is used twice, it breaks even at length 6, though spacing and precedence issues can change that.
(In the example, if the original variable s is not used, it's shorter to do
g w=...
f=g.words

but that's not true for binding more complex expressions.)

Isn’t this sort of a duplicate/special case of this answer?

@Lynn Looking back, it's a special case, but when I read that answer, the Just example made me think it's for pattern-matching to extract from a container, rather than to store on an expression.

Extra note on this one because it came up in some code I was toying with: you can also bind functions this way. In particular, in the example given in this post one could do f s|w<-words=... and use w instead of words any number of times in the following code. This is obvious in hindsight since functions are as good as any other value in Haskell, but it may be something you wouldn't think of at first.

Shorter transpose
To use the transpose function Data.List has to be imported. If this is the only function needing the import, one can save a byte using the following foldr definition of transpose:
import Data.List;transpose
e=[]:e;foldr(zipWith(:))e

Note that the behaviour is only identical for a list of lists with the same length.
I successfully used this here.

If you know the exact size of the list map((<$>[0..k]).(!!)) where k is the size will likely be shorter.

@WheatWizard As written, map((<$>[0..k]).(!!))s computes the identy of a list of lists s. The approach works if we switch s and [0..k], but then (!!) needs to be flipped. I guess simply [map(!!i)s|i<-[0..k]] then beats the point-free approaches. Try it online!

Use (0<$) instead of length for comparisons
When testing if a list a is longer than a list b, one would usually write
length a>length b

However replacing each element of both lists with same value, e.g. 0, and then comparing those two lists can be shorter:
(0<$a)>(0<$b)

Try it online!
The parenthesis are needed because <$ and the comparison operators (==, >, <=, ...) have the same precedence level 4, though in some other cases they might not be needed, saving even more bytes.

I like: void a>void b
Unfortunately, the generic version is not imported by default. :-(

Replace let by lambda
This can usually shorten a lone auxiliary definition that can't be bound with a guard or defined globally for some reason. For example, replace
let c=foo a in bar

by the 3 bytes shorter
(\c->bar)$foo a

For multiple auxiliary definitions, the gain is probably smaller, depending on the number of definitions.
let{c=foo a;n=bar a}in baz
(\c n->baz)(foo a)$bar a

let{c=foo a;n=bar a;m=baz a}in qux
(\c n m->qux)(foo a)(bar a)$baz a

let{c=foo a;n=bar a;m=baz a;l=qux a}in quux
(\c n m l->quux)(foo a)(bar a)(baz a)$qux a

If some of the definitions refer to the others, it is even harder to save bytes this way:
let{c=foo a;n=bar c}in baz
(\c->(\n->baz)$bar c)$foo a

The main caveat with this is that let allows you to define polymorphic variables, but lambdas do not, as noted by @ChristianSievers.
For example,
let f=length in(f["True"],f[True])

results in (1,1), but
(\f->(f["True"],f[True]))length

gives a type error.

It rarely matters, but "semantically equivalent" promises a bit too much. We have polymorpic let, so we can do let f=id in (f 0,f True). If we try to rewrite this with lambda it doesn't type check.

@ChristianSievers That's true, thanks for the note. I edited it in.

Lambdabot Haskell
A language is defined by its implementation, and lambdabot (the IRC bot over at #haskell) imports a ton of common modules by default. No need to spend precious bytes re-implementing your favorite functions from Data.List or Control.Monad, just write Haskell (Lambdabot) instead of Haskell in the title and you're good to go!
Edit:
Here's a list of stuff that it imports by default, which includes, among other things, Control.Arrow, Data.Bits, Data.Ratio, System.Random and {-# LANGUAGE ParallelListComp #-} - go wild!

Online Tools

Try it online!
TIO supports online compilation of Haskell code with the GHC 8.0.2 compiler. As TIO is developed with code golfing in mind it's not just an online interpreter but also offers features like byte count, header and footer sections that do not count towards the total byte count (put your main and test code there), automatic markdown generation for a code golf submission, and more.

pointfree.io
Converts Haskell code to pointfree Haskell code which sometimes is shorter, see this tip.
Note: When dealing with functions that take two or more arguments, the pointfree version generated by pointfree.io often includes the ap function which is not in Prelude. However <*> is an equivalent inline version of ap and contained in Prelude in ghc 7.10 or higher. The same goes for liftM2, which is also only available when importing Control.Monad. The pointfree version of some expression like \x -> f (g x) (h x) is given as liftM2 f g h, though this can equivalently be expressed as f.g<*>h.

pointfree.pages.dev is an alternative site for pointfree.io (which is down at the time of editing).

Hoogle

Hoogle is a Haskell API search engine, which allows you to search many standard Haskell libraries by either function name, or by approximate type signature.

Useful to quickly search the documentation or lookup in which packages a function is included.

Note that TIO currently uses GHC 7.8, so the stuff in this tip is not available.

@Zgarb I asked Dennis if ghc can be updated. Currently one can add import Control.Applicative and/or import Control.Monad into the header on TIO to use <$> ect.

@Zgarb TIO's ghc was updated to 8.0.2 thanks to Dennis.

TIOv2 Alpha was replaced with a fork of TIO Nexus, so GHC8.0.2 should be supported.

Avoid sorting
Haskell doesn't have a built-in sorting in Prelude. It can be accessed with an import:
import Data.List
sort

This also gives you access to functions like sortOn and sortBy, as well as other functions in Data.List. But, many times you don't need the full power of sorting and can make do without an import.
Check if a list is sorted
scanl1 max l==l

This requires the list to be nonempty. As a pointfree predicate:
(==)=<<scanl1 max

You can likewise check if a list is in descending order with scanr1 max l==l.
Sort values lying in a known range
If you know the l contains only, say, digits 0 to 9, you can sort it as:
[d|d<-[0..9],x<-l,x==d]

This allows for duplicates in l. If you know l doesn't have duplicates, or are fine dropping them, you can do:
[d|d<-[0..9],elem d l]

or
filter(`elem`l)[0..9]

These also works if l is a string, enumerating characters as ['\0'..] or [' '..]. The range of characters is very large but bounded.
Min and max
If you just need the smallest or largest element, minimum or maximum will do. You can also check whether n>=maximum l as all(<=n)l, and similarly for minimum.
Sorted index
One use of sorting is to find the index of some value n in sorted order within l. You can instead do that by counting smaller elements:
sum[1|x<-l,x<n]

If x appears more than once, this gives the index of its first appearance in sorted order.

When writing expressions that don't use variables, you don't need to include the function name for scoring purpose. For example:
f=foo.bar

If f is the golfing answer, the byte count is 7 (you can omit f=). It is possible to write it properly with TIO using CPP.
In the header, include:
{-# LANGUAGE CPP #-}
f=\

Example here.

Golfier: Add a -cpp compiler flag.

(Ab)use the Reader Monad/Applicative
There already are comments on pointfree code and one mentioning pure, but I figured I'd make a specific tip for this since I see it a lot.
The Applicative functions in Prelude by default when specialized to functions are as follows
instance Applicative ((->) a) where
    pure = const
    (f <*> g) x = f x (g x)

Note that for this particular type, (=<<) acts almost the same as (<*>), except it takes its second argument flipped (thanks @ØrjanJohansen).
pure is one character shorter than const, as mentioned elsewhere. The especially useful combinator, however, is (<*>). Below are examples of where I've used it recently.
Unique characters
The straightforward way to solve this is
import Data.List
map(\x->(x!!0,length x)).group.sort

But we're here for codegolf, not readable code.
import Data.List
map((,).nub<*>length).group.sort

A contrived function
This comes from a function my coworker wrote that I (unashamedly) golfed until it was unreadable.
Suppose we have
data Ex a b c
  = Ex
    { foo :: [(a,b)]
    , bar :: c}

and we want the natural implementation of a function
f :: Ex a b c -> [(a,c)]

I don't have the original solution (it did involve (&&&) from Control.Arrow, though), but the golfed one using (<*>) is
map.fmap.pure.bar<*>foo

which also abuses the Functor instance of (,) a.
digitSum(n) + n
This golf is part of this answer.
This is a pretty well-golfed function
\n->n+sum[read[d]|d<-show n]

but if we do away with readability and bring in (<*>), we can shave off a character:
foldr((+).read.pure)<*>show
-- = \x -> foldr ((+) . read . pure) x (show x)

do notation
If your function is of the form \x -> (expr) x and (expr) contains some repeated blah x often, you can sometimes save bytes with Reader monad do notation and b<-blah.
Here are some strange examples:
\x->max(div x 3*div x 5^div x 7)x   -- original expression
f x|d<-div x=max(d 3*d 5^d 7)x;f    -- define f=... then use f
\x->max(x!3*x!5^x^7)x;(!)=div       -- define (!)=div
do d<-div;max$d 3*d 5^d 7           -- aha!

\x->product x:filter(/=product x)x      -- original expression
(:)<$>product<*>(filter=<<(/=).product) -- yeah, no...
f x|p<-product x=p:filter(/=p)x;f       -- define f=... then use f
\x->p x:filter(/=p x)x;p=product        -- define p=product
do p<-product;(p:).filter(/=p)          -- aha!

In general, do a<-b;c<-d;e is equivalent to \x->let{a=b x;c=d x}in e x.

Using =<< instead of <*> gives a different parameter order that is sometimes useful.

(<*>) is the S combinator; pure is the K combinator.

The function 0^x
This maps positive integers to 0 and zero to 1. So, it acts a little bit like !x in C-like languages.
It crashes for negative x; in this case you can write 0^x^2, which parses as 0^(x^2).
This is not technically specific to Haskell, but Haskell is quite strict about converting between numbers and booleans compared to some other common code golf languages. It's often shorter to use 0^x and stay in Integer-land than to check x==0.
Even expressions like 0^(x-42)^2 come in handy sometimes (if x==42 then 1 else 0).
Example:
if x==0 then 'B' else 'A'
last$'B':['A'|x==0]
"AB"!!sum[1|x==0]
"AB"!!(0^x^2)
"AB"!!(0^x)       -- if x is never negative

If you need to use the arbitrary precision Integer type, it appears that 0^x can also convert x from Integer to Int for use with (!!)

Partition a string with mapM and words
This function computes all partitions of a given string into nonempty contiguous substrings:
map(words.concat).mapM(\c->[[c],c:" "])

The idea is that the mapM non-deteministically replaces each character c with either "c" or "c ", and the resulting lists are concatenated and split at spaces.
There are two gotchas: the string must not contain spaces (if it contains spaces but not line breaks, use "\n" and lines for one extra byte), and each partition occurs twice in the resulting list (with and without a trailing space, which gets eaten by words).
I've used this technique a couple of times (at least here, here and here).
It's pretty flexible, since you can apply more functions after words to modify the partitions, and/or replace map with another iteration function, like any.

Great idea using string function to split! I'll have to use this sometime. The best general-purpose alternative I found was 45 bytes, 6 longer: foldr(\h t->map([h]:)t++[(h:y):z|y:z<-t])[[]].

When applied directly to some x this can be slightly shortened to words.concat<$>mapM(\c->[[c],c:" "])x .

Use fromEnum instead of ord
fromEnum is already available in Prelude, while ord needs to be imported from Data.Char. This will save you 12 bytes. With subsequent usages you should define an alias like f=fromEnum and use f.

If you use it more than once, you should define an alias with e=fromEnum, which is shorter than import Data.Char and costs 1 byte to use.

@Zgarb: of course, I'm always doing that when writing answers, but for this tip I totally forgot about it.

The same goes for chr and toEnum, however the type of toEnum needs to be forced from context.

Converting to Pointfree
As @Laikoni mentioned in this post, you can use pointfree.io to convert your code to pointfree code. However, if you want to do this conversion manually you can check out this answer on stackoverflow by @luqui, which provides an algorithm:

You need the following combinators, which are in the standard library.
  I have also given their standard names from combinator calculus.
id :: a -> a                                   -- I
const :: a -> b -> a                           -- K
(.) :: (b -> c) -> (a -> b) -> (a -> c)        -- B
flip :: (a -> b -> c) -> (b -> a -> c)         -- C
(<*>) :: (a -> b -> c) -> (a -> b) -> (a -> c) -- S

Work with one parameter at a time.  Move parameters on the left to
  lambdas on the right, e.g.
f x y = Z

becomes
f = \x -> \y -> Z

I like to do this one argument at a time rather than all at once, it
  just looks cleaner.
Then eliminate the lambda you just created according to the following
  rules. I will use lowercase letters for literal variables, uppercase
  letters to denote more complex expressions.

If you have \x -> x, replace with id
If you have \x -> A, where A is any expression in which x does not occur, replace with const A
If you have \x -> A x, where x does not occur in A, replace with A. This is known as "eta contraction".
If you have \x -> A B, then

If x occurs in both A and B, replace with (\x -> A) <*> (\x -> B).
If x occurs in just A, replace with flip (\x -> A) B
If x occurs in just B, replace with A . (\x -> B),
If x does not occur in either A or B, well, there's another rule we should have used already.

And then work inward, eliminating the lambdas that you created.

Sometimes a shortcut with >>= is possible:

If you have \x -> A B x, where x does not occur in A, replace with (\x -> B) >>= A.

in the general case, (\x -> A B x) = join ((\x -> A) <*> (\x -> B)).

@Razetime thanks for the suggestion, it already is mentioned:)

Cheap divisors
The usual way to get the divisors (factors) of n is:
[d|d<-[1..n],mod n d<1]

For example, n=6 gives [1,2,3,6]. But, if you're OK with divisors repeating out of order, you can just do:
gcd n<$>[1..n]

For n=6, this gives [1,2,3,2,1,6]. The code is effectively [gcd k n|k<-[1..n]], takes the greatest common divisor of k with n. These are by definition divisors of n, and each divisor d appears at least once as gcd d n. So, the "set" of divisors is correct. The first appearances are in increasing order, so removing duplicates will match the original code's result.

Define local variables in list comprehensions using singleton lists
For example, rather than writing
[x+y|x<-[1..5],let y=2]

one can write
[x+y|x<-[1..5],y<-[2]]

for a byte less.
This works in do blocks as well, but only in the list context since the [] syntactic sugar is necessary to come out ahead. (I guess any custom monads with single-letter constructors would benefit from this, too, but I don't think I've ever seen any of those show up in code golf.)

@Brute_Force: I meant only to show an example of how this tip would be used; I did not mean to claim that this particular example is realistic. For a more realistic example, consider \a b->[[r..s]|r<-[a..b],s<-[2*r+7],s>7]

Powerset
The "canonical" way of computing the powerset of a list is Data.List.subsequences.
If it is used only once and applied to a value (as opposed to, say, being fed to map), it's slightly shorter to implement it yourself.
Compare:
import Data.List;subsequences x
concat<$>mapM(\a->[[a],[]])x

This saves 0-3 bytes depending on whether you need a space between subsequences and the argument, and whether the latter expression needs parentheses around it.
If x has the form f<$>y, you can move f inside the lambda to save some more bytes, particularly if f is also defined by a lambda:
import Data.List;subsequences$f<$>y
concat<$>mapM(\a->[[f a],[]])y

import Data.List;subsequences$(\a->a*3+1)<$>y
concat<$>mapM(\a->[[a*3+1],[]])y

It's also possible to compose concat with another function, if you intended to map it over the subsequences anyway:
import Data.List;g<$>subsequences x
g.concat<$>mapM(\a->[[a],[]])x

If you have already imported Control.Monad, you can implement the powerset function in 18-20 bytes with one of
filterM(\_->[0>1..])
filterM$[0>1..]<$id
filterM([0>1..]<$f)
filterM$[0>1..]<$f

The last two variants need another function f :: a -> b to be defined, where [a] is the type of the list (doesn't matter what f does or what b is).
The optimal choice depends on whether such an f is available, and whether you need parentheses around the expression.

Might note that this gives 3 different variations in the ordering of the resulting power set. subsequences uses the order that generalizes to an infinite list, although then it's not really a power set.

Maybe it has some use in some situation (\a->[[a],[]]) has the same length as the point free ((:[[]]).pure).

Use Data.Lists
This package defines a lot of nice functions on lists! It’s like Data.List in base, but fancier.
Importing it costs 18 bytes (import Data.Lists\n).
Here are some nice things it exports, on top of everything from Data.List:
Various shortcuts:

  for              ≡ flip map
  unionOf          ≡ foldr union []
  hasAny e x       ≡ any (`elem` e) x
  countElem i      ≡ length . filter (== i)
  list b f xs      ≡ if null xs then b else f xs
  firstOr x        ≡ list x head
  maxList xs       ≡ list 0 maximum
  catchNull f      ≡ list Nothing (Just . f)
  lastToMaybe      ≡ catchNull last
  chop f           ≡ list [] (\x->let (y,ys)=f x in y:chop f ys)
  pair x y         ≡ guard (length x == length y) >> Just (zip x y)
  pairWith f x y   ≡ guard (length x == length y) >> Just (zipWith f x y)

Split functions:

  splitOn "x" "axbxc"                  ≡ ["a","b","c"]
  endBy ";" "foo;bar;baz;"             ≡ ["foo","bar","baz"]
  splitWhen (<0) [1,3,-4,5,7,-9,0,2]   ≡ [[1,3],[5,7],[0,2]]
  splitOneOf ";.," "foo,bar;baz.gluk"  ≡ ["foo","bar","baz","gluk"]
  endByOneOf ";.," "ae;io.,u,"         ≡ ["ae","io","","u"]
  chunk 3 ['a'..'k']                   ≡ ["abc","def","ghi","jk"]
  replace old new                      ≡ intercalate new . splitOn old

Variants of Data.List functions:

  elemRIndex     ∷ a -> [a] -> Maybe Int   (Rightmost index)
  powerslice     ∷ [a] → [[a]]             (All slices of a list)

  spanList       ∷ ([a] → Bool) → [a] → ([a], [a])
  breakList      ∷ ([a] → Bool) → [a] → ([a], [a])
  takeWhileList  ∷ ([a] → Bool) → [a] → [a]
  dropWhileList  ∷ ([a] → Bool) → [a] → [a]

Data.List.Argmax:

  argmin,         argmax           ∷ Ord b ⇒ (a → b) → [a] →   a
  argmins,        argmaxes         ∷ Ord b ⇒ (a → b) → [a] →  [a]
  argminWithMin,  argmaxWithMax    ∷ Ord b ⇒ (a → b) → [a] → ( a,  b)
  argminsWithMin, argmaxesWithMax  ∷ Ord b ⇒ (a → b) → [a] → ([a], b)

Association list functions: treat [(k, v)] as a pseudo-map type.

  delFromAL l k  ≡ filter ((/= k) . fst) l
  addToAL l k v  ≡ (k, v) : delFromAL l k
  keysAL         ≡ map fst
  hasKeyAL k     ≡ any ((== k) . fst)
  flipAL         ∷ [(k, v)] → [(v, [k])]

Integral to Fractional (e.g. Int to Double)
Instead of using the famous
fromIntegral :: (Integral a, Num b) => a -> b

in many cases
realToFrac :: (Real a, Fractional b) => a -> b

works too. and is two bytes shorter.

There are cases where read.show works too, if GHC can infer the types. (For example: sin$read$show someInt.)

toEnum :: Enum a => Int -> a also works, though slightly more constrained.

Haskell + plumbers
Use the plumbers package for a large collection of infix combinators.
For example,
-- Ungolfed
f (x, y) (z, t) = (x + z, y + t)
-- Golfed (without plumbers)
f(x,y)(z,t)=(x+z,y+t)
-- Golfed (with plumbers)
f=(+)***(+)

Or, let's say we wanted to find the dot product of a list of vectors in the form [(Double, Double)].
-- Ungolfed
g = sum . map (\(x,y) -> x * y)
-- Golfed (without plumbers)
g=sum.map(uncurry(*))
-- Golfed (with plumbers)
g=sum.map((*)$*id)

Plumbers are a great way to pointfree an expression, especially in the middle of a map or a fold.
As a quick note, the way to read these operators is as follows.
($**>^)

Every plumber takes two functions as arguments. The first character specifies how to combine the results of the two functions. A * means to return a tuple, and a $ means to pass the result of the second function to the first function. The remaining characters specify what to do with the remaining arguments.
< Pass the argument to the left but not the right function
> Pass the argument to the right but not the left function
& Pass the argument to both functions
^ Ignore the argument completely
* The argument is a tuple; split it and pass the parts to the left and right functions

I like how plumbers calls itself pointless plumbing combinators.

Helper functions
This is (or will) be a list of generic helper functions that occasionally have to be implemented as part of a bigger solution.

Primality test: p :: Int -> Bool
p n=mod(product[1..n-1]^2)n>0

Binary to decimal: b :: String -> Int
b=foldl(\a x->2*a+read[x])0

Decimal to binary: d :: Int -> String
d n=mapM(\_->"01")[1..n]!!n

More to come.

It might be worth adding two more primality tests: p n=[1|0<-mod n<$>[2..n]]==[1] and p n=all((>0).mod n)[2..n-1]. The former identifies 0 as not prime, the latter is only valid for n>=2. Both can come in handy

Also the ^2 in the primality test is only needed for n==4.

The decimal to binary can be d n=mapM("01"<$d)[1..n]!!n, although that depends on defining it as a function, or having another one-letter Int->something function to put with the <$.

@ØrjanJohansen, some of those tests look similar to Wilson's theorem, but not the same. Where's the square come from?

@dfeuer It's the shortest way to handle the fact that Wilson's product for the number n=4 is 2 (mod n), instead of 0 (mod n) like for all other composites.

The decimal to binary can be further reduced to d=(mapM("01"<$d)[1..8]!!) if your input is an ASCII character.

Use pure to build singletons

pure is one byte shorter than (:[]) or Right (thanks, Ørjan Johansen).
pure.f is one byte shorter than Just .f.
pure is shorter than singleton if you need Data.Sequence for some reason.
As Ørjan Johansen points out, this works for the writer monad: pure a=(mempty,a). This may occasionally be useful for something like (Nothing, a).

(,)mempty popped into my mind as another example... not sure how useful.

Oh, and Right too.

Binary op on two-element list
You can apply a binary operation to a two-element list like:
foldr1(-)[5,3]

to get 5-3, or 2. Note that this operator must output the same type as the input, that is be a -> a -> a. So, foldr1(==)[5,3] doesn't typecheck but foldr1 mod[5,3] does.
You can think of this as a list analogue to uncurry(-)(5,3). It may be useful if you take input as a two-element list or one is produced in an intermediate computation, and it would cost extra bytes to match it to [a,b] to extract the values.
Using foldl1 gives the same result as foldr1. The best way to flip the order of the operands seems to just be to flip the operator.

Fixity declarations are your friends
As we know it is often cheaper to define an operator instead of a function (see this tip), sometimes it pays off to declare a fixity different from the default (infixl 9). Imagine for example the following which is fairly common (57 bytes):
(a:b)!(c:d)=undefined
(a:b)!e=undefined
e!(a:b)=undefined

In that particular case using a fixity declaration is still 1 byte more expensive (58 bytes):
infix 4!
a:b!c:d=undefined
a:b!e=undefined
e!a:b=undefined

As you can see you can use the low fixity to omit several parentheses, if somewhere in your code you have other parentheses that are due to the high default fixity, you can save bytes for these by declaring another fixity.

Note: This might seem like an arbitrary example but it is realistic as you can see in this answer.

Here's another answer that uses this trick.

Use pure instead of const. I saw this in someone else's answer, but I don't know where. Of course, it's often better to use a lambda if it's applied.
There's an occasional one byte shorter trick than the lambda \_->x: Use x<$f where f is any one-letter function that just happens to have the same input type as what you want. Note that this never evaluates f itself at all.

fmap
In the spirit of saving characters using infix operators, you could save a couple by replacing something like:
map show [1..9]

with:
show<$>[1..9]

Use zip
Often you need to map over a list and apply some function which depends on the index of the argument in the list. while a lot of impure languages who have some sort of map builtin have the index be an optional argument, this is impossible in Haskell. instead, use:
mapWithIndex f xs === f<$>zip[0..]xs
                  === [f i x|(i,x)<-zip[0..]xs] {- inlinable version -}
                  === zipWith f[0..]xs
mapWithIndex f    === (f<$>).zip[0..]           {- points free version -}

(This also gives us 1-based indexing for free!)
Often this combines well within list comprehensions, where even a builtin mapWithIndex won't help:
    [ ... | ..., (i,x)<-zip[0..]xs, ...]

Other times, you really want to use the nonexistant equivalent maximumOn of sortOn, but the import is too many bytes, or using maximumBy is too many bytes too. instead, use*:
sortOn f xs === snd$sort$(f>>=(,))<$>xs
            === snd$sort[(f x,x)|x<-xs]   {- inlinable version -}
sortOn f    === snd.sort.(f>>=(,)<$>)     {- points free version -}

Note that sometimes you will need both the best x and its f x, in which case you can get rid of three bytes and have it computed for you for free!
many other uses for this combination are possible too.

I don't think f<$>zip[0..]xs works as [f i x|(i,x)<-zip[0..]xs]. You'd need uncurry f<$>zip[0..]xs, since f is being given tuples of (i,x). It would work to do zipWith f[0..]xs,

@xnor as the code golfer, you can modify your f whatever way fits best. We're not writing library functions here.

@xnor Oh, that's a way I haven't thought of! I'll add it.

Oh, you're saying that f is the outer function that you're defining in the code golf challenge, and so you can choose whether it's curried or takes a tuple? That definitely works for that case, but it wasn't clear from reading it that it wasn't meant to apply to functions you define as as subpart of your golf.

@xnor even if f  isn't a function you defined yourself, then the fact that both options are possible is useful, because using curry or uncurry will probably be longer than just switching to one of the other options presented here.

Use empty let instead of otherwise/True
x&y|x=y|let=x  -- Boolean and

While it is no shorter than using 1>0 and usually it makes more sense to use the guard to bind a variable it can be useful when there are source restrictions or the prelude is not in scope.
This works because let statements in guards behave as always true and an empty let is valid.
Empty let also works in list comprehensions, but I believe it completely useless for golfing in that position as it can be omitted.

Pattern match inside list comprehensions
Suppose you have code that looks like (imports for purpose of demonstration)
import Data.List (lookup)
import Data.Maybe (catMaybes)

ys = [(1,"a"), (3, "b"), (5, "c"), (7, "d")]
catMaybes [lookup x ys | x <- [1..10]]

You can change this to
[y | x <- [1..10], Just y <-[lookup x ys]]

I found it particularly helpful when I was
pattern matching in a function definition
f (x:xs) = [foo x x'| x' <-[1..10]]
f [] = []

when I could instead put the pattern matching logic inside the list comprehension.
f lst = [foo x x' | x:xs<-[lst], x'<-[1..10]]

This works because incomplete pattern matches are desuarged to mfail
instead of error in do notation, so for things like the list monad,
we get the empty list. It can be used with do notation for other
monads, too, although pure is probably the shortest alternative to [].
f :: [Int] -> Maybe String
f lst = do
  1:xs <- pure lst
  pure "one"

Some notes: (1) lookup itself can be replaced by pattern matching if you know there cannot be more than one match. (2) You don't need parentheses around patterns before <-. (3) You can shorten [foo x x' | (x:xs)<-[lst], x'<-[1..10]] further to [foo x|x:xs<-[lst]]<*>[1..10].

@ØrjanJohansen nice catch on the parentheses, and yeah I’m sure there are other tricks, these were contrived examples to demonstrate the utility.

iterate isn't very good
Defining your own function that returns an infinite list is usually shorter.
Compare:
f x=x*x+x;iterate f a
iterate(\x->x*x+x)a
g x=x:g(x*x+x);g a

Exceptions include when f is a builtin, but remember:

iterate pred a is just [a,pred a..]
iterate(+k)a is just [a,a+k..]

Sometimes I see people write very "Haskell-y" expressions like:
(+5).fst<$>iterate(\(a,b)->(b,a+b+1))(0,1)

But this can be golfed down all the way to:
a#b=b+5:b#(a+b+1);0#1

Endless Char ranges
You can use endless ranges of Chars, and they will still be finite, because there are only 1114111 valid Unicode characters:
['a'..]

producing
"abcdefghijklmnopqrstuvwxyz{|}~\DEL\128\129\130\131\132\133\134\135\136\137\138\139\140\141\142..."

Attempt This Online!
In many cases where you would otherwise use a range such as ['a'..'z'], you may be able to leave off the ending item, if you know the input is constrained to a certain set of characters (e.g. only alphanumeric ASCII)

Avoid Data.List
The function are nice, but imports are costly. If you only need a single function, there are shorter alternatives:
import Data.List;intercalate -- too long
c#s=tail$(c:)=<<s            -- nice, especially when inlined
(tail.).(=<<).(:)            -- if you like unreadable mess
(tail.).((c:)=<<)            -- applied to c

import Data.List;intersperse -- too long
c#s=tail$do d<-s;[c,d]       -- nice
(c:).pure=<<tail             -- a function on the list

Check if the challenge allows for leading and/or trailing newlines. You may be able to omit the tail.


text:
Match strings whose length is a fourth power
Within the scope of this question, let us consider only strings which consist of the character x repeated arbitrary number of times.
For example:
<empty>
x
xx
xxxxxxxxxxxxxxxx

(Well, actually it doesn't have to be x - any character is fine as long as the whole string only has 1 type of character)
Write a regex in any regex flavor of your choice to match all strings whose length is n4 for some non-negative integer n (n >= 0). For example, strings of length 0, 1, 16, 81, etc. are valid; the rest are invalid.
Due to technical limitations, values of n bigger than 128 are hard to test against. However, your regex should, at least in theory, work with all numbers up to infinity (assuming unlimited memory and computation time).
Note that you are not allowed to execute arbitrary code in your regex (to Perl users). Any other syntax (look-around, back-reference, etc.) is allowed.
Please also include a short explanation about your approach to the problem.
(Please don't paste auto generated regex syntax explanation, since they are useless)
This is code-golf. For each regex flavor, the regex compatible with that flavor having the shortest length in bytes wins in that category. The shortest of all of the answers wins overall.
Standard loopholes are disallowed.

Note that this challenge was originally posted as a puzzle, not code-golf. But the actual answers basically treated it as code-golf anyway, just without actually specifying their sizes in bytes. That has now been fixed, to give the challenge objective winning criteria and make it on-topic for CGCC.
Scoreboard

Regex engine(s)
Length in bytes / Winner(s)

ECMAScript
41 – DC.223051

ECMAScript / Python or better
43 – DC.223051

Boost
43 – DC.223051

Python
43 – DC.223051

Python (with regex)
43 – DC.223051

Ruby
43 – DC.223051

Perl
32 – DC.223048

Java
32 – DC.223048

PCRE
35 – DC.223129, DC.223048

Perl / PCRE
35 – DC.223129, DC.223048

PCRE1 / PCRE2 v10.33 or earlier
34 – DC.223129

PCRE2 v10.34 or later
32 – DC.223048

.NET
32 – DC.223048

Perl / Java / PCRE v10.34 or later / .NET
32 – DC.223048

Perl / Java / PCRE / .NET
35 – DC.223048

Perl / Java / PCRE / .NET, no lookarounds
39 – primo

"xx" isn't valid, is it?

@KendallFrey: Nope. It is not valid.

@nhahtdh do you think there is a possible answer to that?

@xem: I have found and verify the answer up to 2^16.

you mean lengths up to 2^16 power 4?

@xem: I mean I tested against string length 0 to 2^16. Which means n was from 0 to 16.

I'm pretty sure this is impossible using "true" regular expressions; it's easy to prove (e.g. by the Myhill-Nerode theorem) that the language of strings whose length is a fourth power is not regular. You're going to need some kind of "extended" regexps to solve this.

@IlmariKaronen: This question does not limit the syntax to theoretical regular expression. Just that it doesn't allow arbitrary code execution as allowed in Perl. Other stuffs such as backref, etc. are allowed

Am I right in assuming that you know a solution to this in at least one regex flavour?

@Timwi Yup, he knows. I've found the solution for n^2, now I need to work it out for n^4 :)

@Timwi: Yes. Java, PCRE (probably Perl also, but can't test), .NET. Mine doesn't work in Ruby/JS, though.

In your post you say that "strings of length 0, 1, 16, 81, etc. are valid". Even if I assume you meant 64=4^3 instead of 81-3^4 I still have to ask, why is the empty string allowed?

@Kaya: I think you misunderstood my question. I am asking for length n to the 4th power (n^4). I even wrote that in the question. Empty string is allowed, since 0^4 = 0.

For sure--thanks for the clarification. This is indeed what occurred.

This question has been added to the Stack Overflow Regular Expression FAQ, under "Advanced Regex-Fu".

@n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ : are we allowed to substring the input to quartic root of its length, then use string-squaring to regex square it twice and see if it matches input length ? so something like this : mawk 'function ___(__,_) { return __!~".." || (_=length(__))==length(substr(_=substr(__,(_=int(_^(_+=_^=_<_)^-_))^(_<_),_), gsub(".",_,_),-gsub(".",_,_))_) }($2=___($2))'  1 1 16 1 81 1 256 1 625 1 1296 1 2401 1 4096 1 6561 1 10000 1

@RAREKpopManifesto All the computation must be done in a regex. What you have shown is an AWK program that uses some regex functionality.

@Deadcode : can the regex itself be dynamically generated like this ? :: nice jot 65536  | mawk2 '(OFS=substr(__=$!_,length(__)+(NF=_)))^!(NF=++__)' FS='\n' | gcat -n | gawk -b 'function ___(__,_) { return __~"^(.?|."(_="{"int(length(__)^(_+=++_)^-_)"}")_ (_)_ ")$" } $2=___($2)' 1 1 16 1 81 1 256 1 625 1 1296 1 2401 1 4096 1

because technically the criteria above only forbade code execution DURING the regex  run, which doesn't apply to awk since awk's regex engine lacks that capability entirely, but at the same time, the criteria also never forbade code execution for generation of the regex string itself. so far i've tested up to N=33 (way above the golfing requirement), and still works

@RAREKpopManifesto If you generate a regex using other code, then the length of the generated regex is what you will be scored on, not the length of the code that generated it. And it can't be generated differently depending on the input; there needs to be just one regex that matches all fourth powers.

@Deadcode : so does the 2nd code i mentioned above qualify ? i tested all N from 0 to 33 so far (an input string length of 1,185,921) and it works as expected. prior to the gawk -b call, the stuff before it generates the test cases, and doesn't belong to the solution itself. It also circumvents a major gawk hard limit of {m} of {255} since gawk allows you chain them up, and hard limit only applies per brace pair

. Also unlike other solutions that require hard-coded difference, this code only requires a tiny modification to enable measuring any power ( and accept the power itself as a function input) w/o all the coeffiecients pre-computed

@Deadcode : to be ultra lazy one could barely do ^.?$|^.{2,16}{2,16}{2,16}{2,16}$ as the universal regex of 4th power up to N == 16 but it's also slow as f*****

Perl / PCRE / .NET, 66 bytes
This (ir)regular expression seems to work.
^((?(1)((?(2)\2((?(3)\3((?(4)\4x{24}|x{60}))|x{50}))|x{15}))|x))*$

This regex is compatible with PCRE, Perl, .NET flavors.
This basically follows a "difference tree" (not sure if there's a proper name for it), which tells the regex how many more x's to match for the next fourth power:
1     16    81    256   625   1296  2401 ...
   15    65    175   369   671   1105 ...
      50    110   194   302   434 ...
         60    84    108   132 ...
            24    24    24 ...  # the differences level out to 24 on the 4th iteration

\2, \3, \4 stores and updates the difference as shown on the 2nd, 3rd and 4th rows, respectively.
This construct can easily be extended for higher powers.
Certainly not an elegant solution, but it does work.

+1. Great answer. Although this answer is different from mine (it uses conditional regex, while mine does not), it has the same spirit as my solution (exploiting the difference tree and make use of the forward-declared back-reference of some regex engines).

neat idea re difference tree. for squares the tree is 1 4 9 16 ... 3 5 7 ... 2 2 2, right?

@Sparr thanks, and yes

Perl / Java / PCRE / .NET, 39 bytes
Another Solution
This is, in my opinion, one of the most interesting problems on the site. I need to thank deadcode for bumping it back up to the top.
^((^|xx)(^|\3\4\4)(^|\4x{12})(^x|\1))*$

39 bytes, without any conditionals or assertions... sort of. The alternations, as they're being used (^|), are a type of conditional in a way, to select between "first iteration," and "not first iteration."
This regex can be seen to work here: http://regex101.com/r/qA5pK3/1
PCRE interprets the regex correctly, and it has also been tested in Perl up to n = 128, including n4-1, and n4+1.

Definitions
The general technique is the same as in the other solutions already posted: define a self-referencing expression which on each subsequent iteration matches a length equal to the next term of the forward difference function, Df, with an unlimited quantifier (*). A formal definition of the forward difference function:
\$D_f(n)=f(n+1)-f(n)\$
Additionally, higher order difference functions may also be defined:
\$D_f^2(n)=D_f(n+1)-D_f(n)\$
Or, more generally:
\$D_f^k(n)=D_f^{k-1}(n+1)-D_f^{k-1}(n)=\sum\limits_{i=0}^k{(-1)^i}{k\choose i}f(n+k-i)\$
The forward difference function has a lot of interesting properties; it is to sequences what the derivative is to continuous functions. For example, Df of an nth order polynomial will always be an n-1th order polynomial, and for any i, if Dfi = Dfi+1, then the function f is exponential, in much the same way that the derivative of ex is equal to itself. The simplest discrete function for which f = Df is 2n.

f(n) = n2
Before we examine the above solution, let's start with something a bit easier: a regex which matches strings whose lengths are a perfect square. Examining the forward difference function:
\$D_f=[1,3,5,7,9,\dots]=2n+1\$
Meaning, the first iteration should match a string of length 1, the second a string of length 3, the third a string of length 5, etc., and in general, each iteration should match a string two longer than the previous. The corresponding regex follows almost directly from this statement:
^(^x|\1xx)*$

It can be seen that the first iteration will match only one x, and each subsequent iteration will match a string two longer than the previous, exactly as specified. This also implies an amazingly short perfect square test in perl:
(1x$_)=~/^(^1|11\1)*$/

This regex can be further generalized to match any n-gonal length:
Triangular numbers:
^(^x|\1x{1})*$
Square numbers:
^(^x|\1x{2})*$
Pentagonal numbers:
^(^x|\1x{3})*$
Hexagonal numbers:
^(^x|\1x{4})*$
etc.

f(n) = n3
Moving on to n3, once again examining the forward difference function:
\$D_f=[1,7,19,37,61,\dots]=3n^2+3n+1\$
It might not be immediately apparent how to implement this, so we examine the second difference function as well:
\$D_f^2=[6,12,18,24,30,\dots]=6n+6\$
So, the forwards difference function does not increase by a constant, but rather a linear value. It's nice that the initial ('-1th') value of Df2 is zero, which saves an initialization on the second iteration. The resulting regex is the following:
^((^|\2x{6})(^x|\1))*$

The first iteration will match 1, as before, the second will match a string 6 longer (7), the third will match a string 12 longer (19), etc.

f(n) = n4
The forward difference function for n4:
\$D_f=[1,15,65,175,369,\dots]=4n^3-6n^2+4n-1\$
The second forward difference function:
\$D_f^2=[14,50,110,194,302,\dots]=12n^2-24n+14\$
The third forward difference function:
\$D_f^3=[36,60,84,108,132,\dots]=24n+36\$
Now that's ugly. The initial values for Df2 and Df3 are both non-zero, 2 and 12 respectively, which will need to be accounted for. You've probably figured out by now that the regex will follow this pattern:
^((^|\2\3{b})(^|\3x{a})(^x|\1))*$

Because the Df3 must match a length of 12 on the second iteration, a is necessarily 12. But because it increases by 24 each term, the next deeper nesting must use its previous value twice, implying b = 2. The final thing to do is initialize the Df2. Because Df2 influences Df directly, which is ultimately what we want to match, its value can be initialized by inserting the appropriate atom directly into the regex, in this case (^|xx). The final regex then becomes:
^((^|xx)(^|\3\4{2})(^|\4x{12})(^x|\1))*$

Higher Orders
A fifth order polynomial can be matched in with the following regex:
^((^|\2\3{c})(^|\3\4{b})(^|\4x{a})(^x|\1))*$
f(n) = n5 is a fairly easy excercise, as the initial values for both the second and fourth forward difference functions are zero:
^((^|\2\3)(^|\3\4{4})(^|\4x{30})(^x|\1))*$

For six order polynomials:
^((^|\2\3{d})(^|\3\4{c})(^|\4\5{b})(^|\5x{a})(^x|\1))*$
For seventh order polynomials:
^((^|\2\3{e})(^|\3\4{d})(^|\4\5{c})(^|\5\6{b})(^|\6x{a})(^x|\1))*$
etc.
Note that not all polynomials can be matched in exactly this way, if any of the necessary coefficients are non-integer. For example, n6 requires that a = 60, b = 8, and c = 3/2. This can be worked around, in this instance:
^((^|xx)(^|\3\6\7{2})(^|\4\5)(^|\5\6{2})(^|\6\7{6})(^|\7x{60})(^x|\1))*$

Here I've changed b to 6, and c to 2, which have the same product as the above stated values. It's important that the product doesn't change, as a·b·c·… controls the constant difference function, which for a sixth order polynomial is Df6. There are two initialization atoms present: one to initialize Df to 2, as with n4, and the other to initialize the fifth difference function to 360, while at the same time adding in the missing two from b.

Which engines have you tested this on?

I finally understand what is going on. Indeed the only thing needed is support for forward-reference. +1

@nhahtdh ahh, you're right. Forward-references aren't necessarily a universal feature either.

Excellent! I love how short, simple and easy to understand this is. With its shallow nesting, it is easy to calculate by hand how it will behave. Also, it is equally as fast as Volatility's and nhahtdh's solutions. And I love your detailed explanation, including the demonstration that this can even be extended to polynomials. I'd give bonus points if I could.

@Lynn thanks! Was not expecting that...

I managed to match your answer's 39 byte length!

ECMAScript / Perl / Java / Python / Ruby / PCRE / .NET, 50 bytes
Here is a solution that does not use conditionals, forward-declared or nested backreferences, lookbehind, balancing groups, or regex recursion. It only uses lookahead and standard backreferences, which are very widely supported. I was inspired to operate under these limitations due to Regex Golf, which uses the ECMAScript regex engine.
The way this 50 byte regex works is conceptually rather simple, and completely different than all the other submitted solutions to this puzzle. It was surprising to discover that this kind of mathematical logic was expressible in a regex.
      \2                     \4  \5
^((?=(xx+?)\2+$)((?=\2+$)(?=(x+)(\4+)$)\5){4})*x?$

(Capture groups are labeled above the regex)
The regex can be generalized to any power simply by replacing the 4 in {4} with the desired power.
Try it online! - ECMAScript (SpiderMonkey)
Try it online! - ECMAScript (Node.js - faster)
Try it online! - Perl (faster still)
Try it online! - Java
Try it online! - Python
Try it online! - Ruby
Try it online! - PCRE (fastest)
Try it online! - .NET
It works by repeatedly dividing away the smallest fourth power of a prime that the current value is divisible by. As such the quotient at each step is always a fourth power, iff the original value was a fourth power. A final quotient of 1 indicates that the original value was indeed a fourth power; this completes the match. Zero is also matched.
First it uses a lazy capture group \2 to capture the number's smallest factor larger than 1. As such, this factor is guaranteed to be prime. For example, with 1296 (6^4) it will initially capture \2 = 2.
Then, at the beginning of a loop that is repeated 4 times, it tests to see if the current number is divisible by \2, with (?=\2+$). The first time through this loop, this test is useless, but its purpose will become apparent later.
Next inside this inner loop, it uses the greedy capture group \4 to capture the number's largest factor smaller than itself: (?=(x+)(\4+)$). In effect this divides the number by its smallest prime factor, \2; for example, 1296 will initially be captured as \4 = 1296/2 = 648. Note that the division of the current number by \2 is implicit. While it is possible to explicitly divide the current number by a number contained in a capture group (which I only discovered four days after posting this answer), doing this would make for a slower and harder-to-understand regex, and it is not necessary, since a number's smallest factor larger than 1 will always match up with its largest factor smaller than itself (such that their product is equal to the number itself).
Since this kind of regex can only "eat away" from the string (making it smaller) by leaving a result at the end of the string, we need to "move" the result of the division to the end of the string. This is done by capturing the result of subtraction (the current number minus \4), into the capture group \5, and then, outside the lookahead, matching a portion of the beginning of the current number corresponding to \5. This leaves the remaining unprocessed string at the end matching \4 in length.
Now it loops back to the beginning of the inner loop, where it becomes apparent why there is a test for divisibility by the prime factor. We have just divided by the number's smallest prime factor; if the number is still divisible by that factor, it means the original number might be divisible by the fourth power of that factor. The first time this test is done it is useless, but the next 3 times, it determines if the result of implicitly dividing by \2 is still divisible by \2. If it is still divisible by \2 at the beginning of each iteration of the loop, then this proves that each iteration divided the number by \2.
In our example, with an input of 1296, this will loop through as follows:
\2 = 2
\4 = 1296/2 = 648
\4 = 648/2 = 324
\4 = 324/2 = 162
\4 = 162/2 = 81
Now the regex can loop back to the first step; this is what the final * does. In this example, 81 will become the new number; the next loop will go as follows:
\2 = 3
\4 = 81/3 = 27
\4 = 27/3 = 9
\4 = 9/3 = 3
\4 = 3/3 = 1
It will now loop back to the first step again, with 1 as the new number.
The number 1 cannot be divided by any prime, which would make it a non-match by (?=(xx+?)\2+$), so it exits the top-level loop (the one with * at the end). It now reaches the x?$. This can only match zero or one. The current number at this point will be 0 or 1 if and only if the original number was a perfect fourth power; if it is 0 at this point, it means that the top-level loop never matched anything, and if it is 1, it means the top-level loop divided a perfect fourth power down until it wasn't divisible by anything anymore (or it was 1 in the first place, meaning the top-level loop never matched anything).
It's also possible to solve this in 49 bytes by doing repeated explicit division (which is also generalized for all powers – replace the desired power minus one into the {3}), but this method is far, far slower, and an explanation of the algorithm it uses is beyond the scope of this Answer:
^((x+)((\2(x+))(?=(\4*)\2*$)\4*(?=\5$\6)){3})?x?$

Try it online!

From my testing (up to length 1024), it seems that it is correct. However, the regex is too slow - it takes a lot of time just to match length 16^4, so it is very hard to verify for large number. But since performance is not required, I'll upvote when I understand your regex.

Your regex and Volatility's are awesome. Their speed and brevity amaze me, both of them matching 100000000 in 7.5 seconds on my i7-2600k, much faster than I would have expected a regex to be.
My solution here is on a totally different order of magnitude, as it takes 12 seconds to match 50625. But the goal with mine was not speed, but rather, accomplishing the job in minimal code length using a much more limited set of operations.

Our answers are fast, since they barely do any backtracking. Yours do a lot of backtracking in ((((x+)\5+)\4+)\3+)\2+$. Yours is also amazing in its own way, since I can't even think of how to match a square number without forward-declared backreference.

By the way, this question is not code-golf, but a puzzle. I don't judge solution by code length.

Oh. That explains why you used (?:). So should I edit my answer to make the optimized version the primary one?

Feel free to do so. As a suggestion, you might want to insert parts of the regex into your explanation, so that it would be easier to follow.

After my optimizations, this regex now matches 234256=22^4 faster than it formerly matched 50625=15^4. (Still nowhere near as fast as the solutions using forward-declared/nested backreferences.)

Perl / Java / PCRE / .NET, 53 bytes
Solution
^((?=(^|(?<=^x)x|xx\2))(?=(^|\2\3))(^x|\4\3{12}xx))*$

This regex is compatible with Java, Perl, PCRE and .NET flavors. This regex uses quite a range of features: look-ahead, look-behind and forward-declared back-reference. Forward-declared back-reference kinds of limits the compatibility of this regex to a few engines.
Explanation
This solution makes use of the following derivation.
By fully expanding the summation, we can prove the following equality:

Let us combine the summation on the left-hand-side:

Subtract the 2 equations (top equation minus bottom equation) and then combine the summations on the left-hand-side, then simplify it:

We obtain the difference between consecutive fourth powers as power sum:

This means that the difference between consecutive fourth powers will increase by (12n2 + 2).
To make it easier to think, referring to the difference tree in Volatility's answer:

The right-hand-side of the final equation is the 2nd row in the difference tree.
The increment (12n2 + 2) is the 3rd row in the difference tree.

Enough mathematics. Back to the solution above:

The \2 capturing group maintains a series of odd number to calculate i2 as seen in the equation.
Precisely speaking, the length of the \2 capturing group will be 0 (unused), 1, 3, 5, 7, ... as the loop iterates.
(?<=^x)x sets the initial value for the odd number series. The ^ is just there to allow the look-ahead to be satisfied in the first iteration.
xx\2 adds 2 and advance to the next odd number.

The \3 capturing group maintains the square number series for i2.
Precisely speaking, the length of the \3 capturing group will be 0, 1, 4, 9, ... as the loop iterates.
^ in (^|\2\3) sets the initial value for the square number series. And \2\3 adds the odd number to the current square number to advance it to the next square number.

The \4 capturing group (outside any look-ahead and actually consume text) matches the whole right-hand-side of the equation we derived above.
^x in (^x|\4\3{12}xx) sets the initial value, which is + 1 the right-hand-side of the equation.
\4\3{12}xx adds the increase in difference (12n2 + 2) using n2 from capturing group \3, and match the difference at the same time.

This arrangement is possible due to the amount of text matched in each iteration is more than or equal to the amount of text needed to execute the look-ahead to construct n2.

.NET, 39 37 bytes
^(?=((?>^((?<-1>x)+|x)|\1\2\2))*$){2}

Try it online!
Not only does this outgolf primo's amazing answer, but it runs at very close to exactly the same speed under .NET's regex engine.
This solution uses the .NET-specific feature of balanced groups, where every time a group is captured, it's pushed onto the stack for that particular group, and can then be popped off the same number of times. The popping is done in (?<-1>...) above.
This regex works by:

Asserting that \$N/\2\$ is a perfect square, using a perfect analogy of the ^(\1xx|^x)*$ perfect square regex (which uses a nested backreference), and in so doing, pushing capture group \2 onto the stack the same number of times as \$\sqrt{N/\2}\$. This is done with capture group \$\2=1\$.
Redefining capture group \$\2\$ to actually be \$\sqrt N\$ as found by the first main loop iteration, when we pop all copies of \1 off the stack at the beginning of the second iteration of the main loop. Then we assert \$N/\2\$ to be a perfect square using this new definition of \$\2\$.

So it's basically a double square root, like my two other recent answers to this challenge, but this time using .NET's balanced groups to take the square root. (Also, it doesn't return the fourth root in a capture group, just the square root in \2.)
And like my 41 byte ECMAScript answer, it can be modified to match \$8\$th powers, \$16\$th powers, etc., by changing the 2 in {2} to \$log_2 n\$ to match \$n\$th powers.
^   # tail = N = input number
# Main loop - Execute the following in an lookahead, so that on the second iteration
# we can start again from zero.
(?=
    # Capture group \1:
    # Run the following inner loop; for every iteration, push the captured contents
    # onto the balanced group stack for \1. This will later be used as a count.
    # And since this is a loop with a minimum iteration count of zero, regardless of
    # what is done inside, we're guaranteed to be able to match N=0.
    (
        # Evaluate the following in an atomic group, because otherwise the regex engine
        # would backtrack into it, changing the value of \2.
        (?>
            # Execute this if and only if we're on the first iteration of this inner loop.
            # The atomic group around it prevents the other alternative from being taken.
            ^
            # Define \2 to be one of the following two:
            (
                # Pop all copies of \1 off the stack, asserting that at least one
                # was pushed. If this is the first iteration of the main loop, \1
                # has not yet captured anything, and this won't match (and thus will
                # go to the next alternative below). This also clears \1's value,
                # allowing the next iteration of the main loop to start off properly.
                (?<-1>x)+
            |
                # \2 = 1
                x
            )
        |
            # If \1 has a value (which implies \2 also has a value), then \1 = \1 + \2*2;
            # tail -= \1. On the Kth iteration, this will give us head = K^2 * \2. This
            # uses the fact that (n+1)^2 - n^2 = 2n + 1. The 1 comes from \2's initial
            # value.
            \1\2\2
        )
    )*      # Loop the above zero or more times
    $       # Assert tail == 0
){2}    # Loop the main loop above exactly twice

Perl / PCRE2 v10.34 or later, 41 40 38 37 35 33 bytes
^(?=(?|^((\1|x))|\1(\1\2))*+$){2}

Try it online! - Perl
Try it on regex101 / Attempt This Online! - PCRE2
This is a port of the .NET version, using group-building (with a nested backreference) instead of a balanced group. Thanks to the use of a branch reset group (?|...) to reset the value of \2 beteween iterations of the main loop, it too can be modified to match \$8\$th powers, \$16\$th powers, etc., by changing the 2 in {2} to \$log_2 n\$ to match \$n\$th powers. Commented version to come.
Perl / PCRE, 41 40 38 37 35 bytes
^((?=(?|^((\2|x))|\2(\2\3))*+$)){2}

Try it online! - Perl
Try it online! - PCRE1
Try it online! / Attempt This Online! - PCRE2
PCRE1 and earlier versions of PCRE2 did not support quantifying a lookaround, automatically short-circuiting a loop count of \$2\$ or more to be \$1\$. So this version needs to wrap the lookaround in a dummy group in order to quantify it.
Not that it was necessary – but because this challenge and primo's answer talk about testing up to \$128^4\$, I decided to do a test run on this regex. I tested it on all integers from \$0\$ to \$130^4\$ inclusive (that's all integers in that range, not just \$n^4-1\$, \$n^4\$, and \$n^4+1\$) using RegexMathEngine, and there were no false positives or negatives. It took about 4 days of computing time, single-threaded.
PCRE1 / PCRE2 v10.33 and earlier, 36 34 bytes
^((?=(?|^((\2|x))|\2(\2\3))*$)){2}

Try it online! - PCRE1
Try it online! - PCRE2 v10.33
PCRE1 automatically forces capture groups with nested backreference(s) to be atomic, thus allowing us to save 1 byte by omitting the possessive quantifier. Early versions of PCRE2, like the one still on TIO, had the same behavior.
.NET, 38 36 bytes
^(?=(?>^((?<2>\2|x))|\2(\2\1))*$){2}

Try it online!
This is the Perl / PCRE version backported to .NET, using its feature of recapturing numbered groups by using the number as a name, seen as (?<2>...) above.
Perl / Java / PCRE2 v10.34 or later, 41 39 37 bytes
^(?=(^(\3?x)|(?=(\3?x))\1\2\2)*+$){2}

Try it online! - Perl
Try it online! - Java
Try it on regex101 / Attempt This Online! - PCRE2
Unfortunately, without the branch reset group, it cannot be generalized by changing the {2} to anything higher, because the value of \3 is not reset from iteration to iteration. The only way I can think of to generalize in that way makes it much longer, at 55 53 bytes:
^(?=(^(\4?x)(?=(x*))|(?=(((?!\3)\4)?x))\1\2\2)*+$){2}

Try it online! - Java
Perl / Java / PCRE2 v10.34 or later / .NET, 40 bytes
^(?=((?>^(\3?x)|(?=(\3?x))\1\2\2))*$){2}

Try it online! - Perl
Try it online! - Java
Try it on regex101 / Attempt This Online! - PCRE2
Try it online! - .NET
To make the regex fully general to all four of these engines (ignoring PCRE1, because it's an outdated version of the same engine), we must not use balanced groups, recaptured groups, branch reset groups, or possessive quantifiers.
It is possible shorten the regex, while still supporting this exact set of regex engines, by dropping the pretense of a 2-iteration loop and doing the two stages separately.

Very nice improvements!

ECMAScript, 41 bytes
^((?=(x(x*)|)(?=(\2*)\3+$)(\2*$\4))\5){2}

Try it online! - ECMAScript (SpiderMonkey)
Try it online! - ECMAScript (Node.js - faster)
Try it online! - .NET, in ECMAScript emulation mode
This uses a "higher technology" than my older 50 byte ECMAScript answer (which was my very first post on this site), and unlike its algorithm (which works individually on prime factors), does actual division (or multiplication, depending on how you look at it) in a way that works thanks to the Chinese remainder theorem, as explained in this post. The upshot of this is that it returns the \$n\$th root in a capture group when asserting a number is an \$n\$th power, whereas the prime-factoring algorithm is completely unaware of what the root was.
This regex takes the square root twice in a row, asserting each time that the input was a perfect square. The same square-testing regex is used in the second answer in this post. It could be modified to take \$8\$th powers, \$16\$th powers, etc., by changing the 2 in {2} to \$log_2 n\$ to match \$n\$th powers.
^                      # tail = N = input number
(
    (?=
        (x(x*)|)       # \2 = potential square root; \3 = \2-1, or unset if \2==0, in
                       #      order to match N=0 using ECMAScript NPCG behavior;
                       # tail = N-\2
        (?=
            (\2*)\3+$  # if \2*\2 == \2+tail, the first match here must result in \4==0
        )
        (\2*$\4)       # assert \2 divides tail, and \4==0; \5 = tool to make tail = \2
    )
    \5                 # tail = \2
){2}                   # Loop the above exactly 2 times

ECMAScript / Python or better, 43 bytes
^((?=(x(x*))(?=(\2*)\3+$)(\2*$\4))\5){2}|^$

This version is NPCG-independent, allowing it to work on a wide variety of regex engines:
Try it online! - ECMAScript (SpiderMonkey)
Try it online! - ECMAScript (Node.js - faster)
Try it online! - Perl
Try it online! - Java
Try it online! - Boost
Try it online! - Python
Try it online! - Python (with regex)
Try it online! - Ruby
Try it online! - PCRE (fastest)
Try it online! - .NET
^                      # tail = N = input number
(
    (?=
        (x(x*))        # \2 = potential square root, which must be positive; \3 = \2-1;
                       # tail = N-\2
        (?=
            (\2*)\3+$  # if \2*\2 == \2+tail, the first match here must result in \4==0
        )
        (\2*$\4)       # assert \2 divides tail, and \4==0; \5 = tool to make tail = \2
    )
    \5                 # tail = \2
){2}                   # Loop the above exactly 2 times
|^$                    # Allow us to match N=0, which can't be matched above

Perl / Java / PCRE / .NET, 35 bytes
((\2x|^x)+)\1(\3xx|x(?=\2$))+$|^x?$

This beats primo's solution by 4 bytes while supporting the exact same set of regex engines.
Try it online! - Perl
Try it online! - Java
Try it online! - PCRE1
Try it online! / Attempt This Online! - PCRE2
Try it online! - .NET
It works by first finding two consecutive triangular numbers whose sum is \$n\$ (using the equivalent of (\1x|^x)+ to find the smaller one), so that \$\sqrt n\$ will be the triangular root of the larger triangular number. Then it tries to match that root as itself being a perfect square, using the equivalent of (\1xx|^x)+$.
If it did not need to match \$0^4\$, the regex would be 34 bytes, and if it didn't need to match \$1^4\$ either, it would be 30 bytes.
                   # tail = N = input number
    (              # \1 = a triangular number T_0; tail -= \1;
                   # \2 = triangular root of \1
        (
            \2x    # On iterations after the first, \2 = \2 + 1
        |
            ^x     # On the first iteration,        \2 = 1
        )+         # Iterate the above any nonzero number of times
    )
    # T_1, the next consecutive triangular number after \1, is \1 + \2 + 1.
    # N is a perfect square iff tail == T_1.
    \1             # tail -= \1
    (
        \3xx       # On iterations after the first, \3 = \3 + 2
    |
        x          # On iterations after the first, \3 = 1
        (?=\2$)    # Assert that this is the first iteration, while
                   # simultaneously asserting that N is a perfect square,
                   # because if tail == \2 here, it will have equalled \2+1
                   # before this loop began.
    )+             # Iterate the above any nonzero number of times
    $              # Assert tail == 0
|
    ^x?$           # Allow us to match N=0 or N=1, which can't be matched above

Alternative 35 bytes:
((\2x|^x\B|^)+)\1(\3xx|x?(?=\2$))+$

This avoids the special cases for \$n\in [0,1]\$ at the end, while working around PCRE1's atomic behavior, by hinting that the group 2 loop should only capture \$1\$ x in its initial iteration if there are more xs following it. This way we can get the same behavior as the 32 byte version below, where both \1 and \2 capture an empty string when \$n\in [0,1]\$ – but unlike that version, this happens for \$n=1\$ without any backtracking.
Perl / Java / PCRE2 v10.34 or later / .NET, 32 bytes
((\2x|^x?)+)\1(\3xx|x?(?=\2$))+$

This drops 3 bytes at the cost of sacrificing support for PCRE1 and older versions of PCRE2, because they automatically force capture groups with nested backreference(s) to be atomic – which would prevent x? from ever matching \$0\$ instead of \$1\$, blocking \$1^4\$ from being matched.
If it did not need to match \$0^4\$, the regex would be 31 bytes.
Try it online! - Perl
Try it online! - Java
Attempt This Online! - PCRE2 v10.40+
Try it online! - .NET

Perl / Java / PCRE / .NET, 39 bytes
^(?=((\2x|^x)*)\1(\2?x)?)(\4\3\3|^\3)*$

This was a stepping stone from 40 bytes to the 35 byte answer above.
Try it online! - Perl / Java / PCRE1 / PCRE2 v10.33 / PCRE2 v10.40+ / .NET
Alternative 39 bytes, slower in most of the regex engines:
^(\1\4\4|^(?=((\3x|^x)*)\2(\3?x)$)\4)*$

Perl / Java / PCRE2 v10.34 or later / .NET, 38 bytes
^(\1\4\4|(?=((\3x|^x?)+)\2(\3x)$)\4)*$

This was a stepping stone from 40 bytes to the 32 byte answer above.
Try it online! - Perl / Java / PCRE2 v10.40+ / .NET
Alternative 38 bytes, slower in most of the regex engines:
(?=((\2x|^x?)+)\1(\2x)?)(\4\3\3|^\3)*$

Perl / Java / PCRE, 39 bytes
^((((\3|^x)xx)*)x?+)(?=(\1*)\2+$)\1*$\5

Try it online! - Perl
Try it online! - Java
Try it online! - PCRE1
Try it online! / Attempt This Online! - PCRE2
This is the same as the 40 byte regex below, but drops .NET support by using a possessive quantifier, x?+ instead of |^$, to match \$0^4\$. This works because x?+ will always consume 1 x if it can, and will only consume 0 xs if \$\it\text{tail}=0\$, which can happen in two ways:

If the input was \$0\$, in which case \1 and \2 will have both captured \$0\$, and the second half of the regex will match.
If the input was nonzero, in which case \2 will have captured the entire nonzero input value, making it impossible for the second half of the regex to match, as \2+ won't be able to match with \$\it\text{tail}=0\$.

Perl / Java / PCRE / .NET, 42 40 bytes
^((((\3|^x)xx)*)x)(?=(\1*)\2+$)\1*$\5|^$

Try it online! - Perl
Try it online! - Java
Try it online! - PCRE1
Try it online! / Attempt This Online! - PCRE2
Try it online! - .NET
This uses the equivalent of ^(\1xx|^x)*$ to match a perfect square using a nested backreference (made more complicated by needing to capture that square minus \$1\$), and then uses a square-testing algorithm which works thanks to the Chinese remainder theorem (which only requires ECMAScript or better, and is the reason for needing to capture the square minus \$1\$), to assert that the captured perfect square is the square root of the inputted number. The latter algorithm is explained in this post, and this exact square-testing regex is used in the second answer in this post.
    ^                    # tail = N = input number
    (                    # \1 = the largest perfect square for which the
                         #      subsequent expression matches; tail -= \1
        (                # \2 = \1 - 1
            (            # \3 = nested backreference
                # On the first iteration,   \3 =  1 + 2 = 3;
                # on subsequent iterations, \3 = \3 + 2
                (\3|^x)
                xx
            )*           # iterate \3 any number of times (may be zero); \2
                         # becomes the total of all these iterations
        )
        x                # \1 = \2 + 1
    )
    # Assert that N == \1^2
    (?=
        (\1*)\2+$        # iff \1*\1 == N, the first match here must capture \5=0
    )
    \1*$\5               # assert \1 divides N-\1, and \5==0
|
    ^$                   # Allow us to match N=0, which can't be matched above

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

authors: n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳

sort: votes