77
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Seeing the number of answers till now, I am in doubt about whether Haskell is even a good language for code golfing or not? \$\endgroup\$ – Animesh 'the CODER' Jan 24 '14 at 10:23
  • 10
    \$\begingroup\$ Why only one tip per answer? Also, every language is a good language for golfing. Just don't always expect to win. \$\endgroup\$ – unclemeat Feb 12 '14 at 0:46
  • 7
    \$\begingroup\$ @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. \$\endgroup\$ – MasterMastic Jun 1 '14 at 12:10
  • 3
    \$\begingroup\$ Special request, String compression. \$\endgroup\$ – J Atkin Feb 20 '16 at 0:07
  • \$\begingroup\$ This is probably not suited as an anwer, but I'm still want to add it here: wiki.haskell.org/Prime_numbers_miscellaneous#One-liners \$\endgroup\$ – flawr May 25 '16 at 19:38

52 Answers 52

45
\$\begingroup\$

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):

¡ ¢ £ ¤ ¥ ¦ § ¨ © ¬ ® ¯ ° ± ´ ¶ · ¸ ¿ × ÷
| improve this answer | |
\$\endgroup\$
  • 11
    \$\begingroup\$ 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. \$\endgroup\$ – Zgarb Oct 15 '15 at 13:35
  • 3
    \$\begingroup\$ 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) \$\endgroup\$ – Esolanging Fruit Nov 12 '17 at 3:13
  • 2
    \$\begingroup\$ 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 \$\endgroup\$ – Angs May 12 '18 at 17:11
29
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
29
\$\begingroup\$

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)

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ also, use multiple guards instead of && when inside a list comprehension. \$\endgroup\$ – John Dvorak Mar 21 '14 at 14:11
  • \$\begingroup\$ Good one Jan - you should make that into an answer, I'll vote for it \$\endgroup\$ – bazzargh Mar 21 '14 at 14:31
  • 7
    \$\begingroup\$ The first example can be further shortened by True => 1>0 \$\endgroup\$ – John Dvorak Feb 22 '16 at 9:10
  • 1
    \$\begingroup\$ in the first example, I assume you mean f a=if a>0 then 3 else 7 \$\endgroup\$ – Cyoce Apr 2 '16 at 1:24
  • \$\begingroup\$ Guard even works if there's no argument in it. \$\endgroup\$ – Xwtek Oct 23 '16 at 12:18
28
\$\begingroup\$

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]]
    
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Annother use I found useful is [0..b]>>[a] instead of replicate a b. \$\endgroup\$ – Wheat Wizard Jun 24 '17 at 3:04
  • 4
    \$\begingroup\$ @WheatWizard a<$[1..b] is even shorter, for replicate. \$\endgroup\$ – Lynn Jul 31 '17 at 9:39
  • \$\begingroup\$ 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. \$\endgroup\$ – dfeuer Dec 5 '17 at 18:51
  • \$\begingroup\$ OTOH, if you need Data.Traversable anyway, the Cartesian product example can be shortened to for["Hh","io",".!"]id. \$\endgroup\$ – dfeuer Dec 5 '17 at 18:53
  • 2
    \$\begingroup\$ (=<<) is in Prelude, actually! I've used it a lot. \$\endgroup\$ – Lynn Dec 5 '17 at 20:08
24
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
24
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 5
    \$\begingroup\$ +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). \$\endgroup\$ – ankh-morpork Jul 10 '15 at 22:20
  • \$\begingroup\$ 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. \$\endgroup\$ – John Dvorak Jul 11 '15 at 5:32
  • 4
    \$\begingroup\$ Funny there is [1..2] in there. that's just [1,2] \$\endgroup\$ – proud haskeller Aug 26 '15 at 8:08
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Angs Nov 7 '16 at 9:04
  • 3
    \$\begingroup\$ You can now use <> instead of mappend, it's now (with GHC 8.4.1) part of the Prelude. \$\endgroup\$ – ბიმო Mar 10 '18 at 15:50
23
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Apr 7 '14 at 11:14
  • \$\begingroup\$ Can anyone explain this? \$\endgroup\$ – MasterMastic Jun 1 '14 at 12:12
  • 2
    \$\begingroup\$ this isn't a good example, i would just golf this as f=max 10. \$\endgroup\$ – proud haskeller Aug 17 '14 at 14:51
  • \$\begingroup\$ @MasterMastic this is just writing if(true) in other languages. in the prelude, otherwise is actually the boolean value True. \$\endgroup\$ – proud haskeller Aug 17 '14 at 15:08
  • 3
    \$\begingroup\$ @PeterTaylor I think this is still valuable for new haskellians (like me) as I first learned to use otherwise. \$\endgroup\$ – flawr Jun 11 '16 at 9:12
22
\$\begingroup\$

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]
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I actually used all of these before, but I didn't think to put them here. \$\endgroup\$ – proud haskeller Aug 26 '15 at 8:10
18
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
16
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
15
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ +1 -- I hadn't even realised that there was a monad instance for functions. that could be very handy :) \$\endgroup\$ – Jules Jul 22 '16 at 19:42
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – ბიმო Jan 5 '18 at 19:02
14
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
14
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
12
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – Jules Jul 22 '16 at 19:47
12
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – proud haskeller Aug 26 '15 at 8:13
  • 1
    \$\begingroup\$ I'm assuming e isn't actually one token but a longer expression that needs $ before it, which is usually the case. \$\endgroup\$ – Lynn Aug 26 '15 at 14:52
12
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Should it be if b then y else x? \$\endgroup\$ – Xwtek Oct 23 '16 at 11:52
  • \$\begingroup\$ @ChristianIrwan Good catch, yes. \$\endgroup\$ – xnor Oct 23 '16 at 22:09
  • \$\begingroup\$ Wouldnt using bool be shorter as you don't need a list comprehension \$\endgroup\$ – Potato44 Jun 20 '17 at 20:17
  • \$\begingroup\$ @Potato44 That's in Data.Bool, which costs bytes to import. \$\endgroup\$ – xnor Jun 20 '17 at 20:39
12
\$\begingroup\$

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.
| improve this answer | |
\$\endgroup\$
11
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Don't you mean making sections of prefix functions? \$\endgroup\$ – Cyoce Apr 2 '16 at 3:15
  • \$\begingroup\$ @Cyoce Yes, of course \$\endgroup\$ – proud haskeller Apr 2 '16 at 6:28
11
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 3
    \$\begingroup\$ This also works inside list comprehensions: [f 1|let f x=x+1]. \$\endgroup\$ – Laikoni Jun 21 '17 at 6:03
11
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
11
\$\begingroup\$

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

Examples: 1, 2

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The second one has A and [] switched. \$\endgroup\$ – Ørjan Johansen Dec 16 '17 at 18:46
  • \$\begingroup\$ @ØrjanJohansen Corrected, thanks! \$\endgroup\$ – Laikoni Dec 16 '17 at 18:48
  • 1
    \$\begingroup\$ Aha! But *> has higher fixity than >> (still a bit low for comfort.) \$\endgroup\$ – Ørjan Johansen Apr 9 '18 at 18:03
10
\$\begingroup\$

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.)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Isn’t this sort of a duplicate/special case of this answer? \$\endgroup\$ – Lynn Aug 9 '16 at 10:27
  • \$\begingroup\$ @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. \$\endgroup\$ – xnor Aug 10 '16 at 10:14
  • \$\begingroup\$ 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. \$\endgroup\$ – Leo Apr 28 at 4:16
10
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
10
\$\begingroup\$

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 = ...
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ 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 \$\endgroup\$ – BlackCap Dec 16 '16 at 18:22
10
\$\begingroup\$

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])[]
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Perhaps scanl(flip(:))[] "abc" = ["","a","ba","cba"] is also worth mentioning – sometimes the prefixes being backwards doesn't matter. \$\endgroup\$ – Lynn May 28 '18 at 10:50
  • 4
    \$\begingroup\$ Ørjan Johansen found a one-byte shorter alternative for prefixes: scanr(\_->init)=<<id \$\endgroup\$ – Laikoni Dec 8 '18 at 17:36
10
\$\begingroup\$

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"
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ ("123">>) is shorter. \$\endgroup\$ – Ørjan Johansen Dec 19 '18 at 16:23
  • \$\begingroup\$ @ØrjanJohansen: Ah damn, it was meant for educational purposes :P (showing that you can join multiple functions, not only two) \$\endgroup\$ – ბიმო Dec 19 '18 at 16:25
  • \$\begingroup\$ By my count 8−11 functions should be 4−11. (Best case if all functions need parentheses with <>.) \$\endgroup\$ – Ørjan Johansen Dec 19 '18 at 16:38
  • 1
    \$\begingroup\$ 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)). \$\endgroup\$ – Ørjan Johansen Dec 19 '18 at 17:37
  • 1
    \$\begingroup\$ @Ø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 ($). \$\endgroup\$ – ბიმო Dec 19 '18 at 17:45
9
\$\begingroup\$

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']
| improve this answer | |
\$\endgroup\$
9
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • 4
    \$\begingroup\$ If n is global, l=n:l;l is the same length and works for (some) longer expressions. (May need whitespace though.) \$\endgroup\$ – Ørjan Johansen Nov 11 '17 at 3:48
  • \$\begingroup\$ @ØrjanJohansen I incorporated it into the post. Thanks! \$\endgroup\$ – totallyhuman Nov 12 '17 at 1:17
8
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Christian Sievers Jan 17 '17 at 21:09
  • \$\begingroup\$ @ChristianSievers That's true, thanks for the note. I edited it in. \$\endgroup\$ – Zgarb Jan 18 '17 at 8:13
8
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.