Tips for golfing in Haskell

76

32

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.

Animesh 'the CODER'

Posted 2014-01-23T19:18:03.520

Reputation: 959

3Special request, String compression. – J Atkin – 2016-02-20T00:07:05.330

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

– flawr – 2016-05-25T19:38:15.770

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

– flawr – 2016-06-11T09:09:31.430

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

– flawr – 2016-07-30T19:16:37.683

1Seeing the number of answers till now, I am in doubt about whether Haskell is even a good language for code golfing or not? – Animesh 'the CODER' – 2014-01-24T10:23:45.417

10Why only one tip per answer? Also, every language is a good language for golfing. Just don't always expect to win. – unclemeat – 2014-02-12T00:46:36.467

6@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. – MasterMastic – 2014-06-01T12:10:54.733

Answers

45

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

¡ ¢ £ ¤ ¥ ¦ § ¨ © ¬ ® ¯ ° ± ´ ¶ · ¸ ¿ × ÷

shiona

Posted 2014-01-23T19:18:03.520

Reputation: 2 889

11Note: 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. – Zgarb – 2015-10-15T13:35:57.833

3This 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) – Esolanging Fruit – 2017-11-12T03:13:58.147

2Sometimes 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 – Angs – 2018-05-12T17:11:47.557

29

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

shiona

Posted 2014-01-23T19:18:03.520

Reputation: 2 889

29

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)

bazzargh

Posted 2014-01-23T19:18:03.520

Reputation: 2 476

6The first example can be further shortened by True => 1>0 – John Dvorak – 2016-02-22T09:10:09.437

1in the first example, I assume you mean f a=if a>0 then 3 else 7 – Cyoce – 2016-04-02T01:24:59.703

Guard even works if there's no argument in it. – Akangka – 2016-10-23T12:18:44.687

2also, use multiple guards instead of && when inside a list comprehension. – John Dvorak – 2014-03-21T14:11:47.360

Good one Jan - you should make that into an answer, I'll vote for it – bazzargh – 2014-03-21T14:31:31.747

28

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]]
    

Lynn

Posted 2014-01-23T19:18:03.520

Reputation: 55 648

1Annother use I found useful is [0..b]>>[a] instead of replicate a b. – Post Rock Garf Hunter – 2017-06-24T03:04:17.947

3@WheatWizard a<$[1..b] is even shorter, for replicate. – Lynn – 2017-07-31T09:39:12.097

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. – dfeuer – 2017-12-05T18:51:15.423

OTOH, if you need Data.Traversable anyway, the Cartesian product example can be shortened to for["Hh","io",".!"]id. – dfeuer – 2017-12-05T18:53:42.210

2(=<<) is in Prelude, actually! I've used it a lot. – Lynn – 2017-12-05T20:08:08.223

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. – flawr – 2017-12-09T20:19:44.193

24

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!

Flonk

Posted 2014-01-23T19:18:03.520

Reputation: 7 621

24

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.

Lynn

Posted 2014-01-23T19:18:03.520

Reputation: 55 648

5+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). – ankh-morpork – 2015-07-10T22:20:47.653

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. – John Dvorak – 2015-07-11T05:32:40.707

4Funny there is [1..2] in there. that's just [1,2] – proud haskeller – 2015-08-26T08:08:46.323

2In 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. – Angs – 2016-11-07T09:04:47.530

2You can now use <> instead of mappend, it's now (with GHC 8.4.1) part of the Prelude. – ბიმო – 2018-03-10T15:50:50.660

@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. – Ørjan Johansen – 2018-04-03T17:59:13.720

Occasionally you can use fail"" instead of Nothing. – dfeuer – 2019-03-14T20:29:09.833

Now I know why FTP was finally accepted. – Lemming – 2020-02-13T22:15:16.150

23

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

Flonk

Posted 2014-01-23T19:18:03.520

Reputation: 7 621

3@PeterTaylor I think this is still valuable for new haskellians (like me) as I first learned to use otherwise. – flawr – 2016-06-11T09:12:04.167

3This 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. – Peter Taylor – 2014-04-07T11:14:16.107

Can anyone explain this? – MasterMastic – 2014-06-01T12:12:06.537

2this isn't a good example, i would just golf this as f=max 10. – proud haskeller – 2014-08-17T14:51:05.277

@MasterMastic this is just writing if(true) in other languages. in the prelude, otherwise is actually the boolean value True. – proud haskeller – 2014-08-17T15:08:32.337

21

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]

Lynn

Posted 2014-01-23T19:18:03.520

Reputation: 55 648

I actually used all of these before, but I didn't think to put them here. – proud haskeller – 2015-08-26T08:10:34.160

18

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.

Lynn

Posted 2014-01-23T19:18:03.520

Reputation: 55 648

16

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.

xnor

Posted 2014-01-23T19:18:03.520

Reputation: 115 687

15

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

Lynn

Posted 2014-01-23T19:18:03.520

Reputation: 55 648

14

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

nyuszika7h

Posted 2014-01-23T19:18:03.520

Reputation: 1 624

14

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.

proud haskeller

Posted 2014-01-23T19:18:03.520

Reputation: 5 866

+1 -- I hadn't even realised that there was a monad instance for functions. that could be very handy :) – Jules – 2016-07-22T19:42:55.890

2Side 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. – ბიმო – 2018-01-05T19:02:26.173

12

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

proud haskeller

Posted 2014-01-23T19:18:03.520

Reputation: 5 866

4Worth 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. – Jules – 2016-07-22T19:47:59.647

12

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.

Lynn

Posted 2014-01-23T19:18:03.520

Reputation: 55 648

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 – proud haskeller – 2015-08-26T08:13:32.260

1I'm assuming e isn't actually one token but a longer expression that needs $ before it, which is usually the case. – Lynn – 2015-08-26T14:52:09.217

12

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

xnor

Posted 2014-01-23T19:18:03.520

Reputation: 115 687

Should it be if b then y else x? – Akangka – 2016-10-23T11:52:06.623

@ChristianIrwan Good catch, yes. – xnor – 2016-10-23T22:09:34.080

Wouldnt using bool be shorter as you don't need a list comprehension – Potato44 – 2017-06-20T20:17:07.863

@Potato44 That's in Data.Bool, which costs bytes to import. – xnor – 2017-06-20T20:39:39.000

11

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.

Zgarb

Posted 2014-01-23T19:18:03.520

Reputation: 39 083

11

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.

Anders Kaseorg

Posted 2014-01-23T19:18:03.520

Reputation: 29 242

3This also works inside list comprehensions: [f 1|let f x=x+1]. – Laikoni – 2017-06-21T06:03:41.243

11

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.

proud haskeller

Posted 2014-01-23T19:18:03.520

Reputation: 5 866

Don't you mean making sections of prefix functions? – Cyoce – 2016-04-02T03:15:28.693

@Cyoce Yes, of course – proud haskeller – 2016-04-02T06:28:56.360

11

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

Zgarb

Posted 2014-01-23T19:18:03.520

Reputation: 39 083

10

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!

totallyhuman

Posted 2014-01-23T19:18:03.520

Reputation: 15 378

4If n is global, l=n:l;l is the same length and works for (some) longer expressions. (May need whitespace though.) – Ørjan Johansen – 2017-11-11T03:48:46.730

@ØrjanJohansen I incorporated it into the post. Thanks! – totallyhuman – 2017-11-12T01:17:45.490

10

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

Laikoni

Posted 2014-01-23T19:18:03.520

Reputation: 23 676

The second one has A and [] switched. – Ørjan Johansen – 2017-12-16T18:46:59.207

@ØrjanJohansen Corrected, thanks! – Laikoni – 2017-12-16T18:48:17.007

1Aha! But *> has higher fixity than >> (still a bit low for comfort.) – Ørjan Johansen – 2018-04-09T18:03:50.237

10

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.

xnor

Posted 2014-01-23T19:18:03.520

Reputation: 115 687

10

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

nimi

Posted 2014-01-23T19:18:03.520

Reputation: 34 639

2It doesn't have to be conditions either, you can do things like this: f xs m | [x] <- xs, Just y <- m, x > 3 = y – BlackCap – 2016-12-16T18:22:56.587

9

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']

Flonk

Posted 2014-01-23T19:18:03.520

Reputation: 7 621

9

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.

Zgarb

Posted 2014-01-23T19:18:03.520

Reputation: 39 083

1It 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. – Christian Sievers – 2017-01-17T21:09:13.577

@ChristianSievers That's true, thanks for the note. I edited it in. – Zgarb – 2017-01-18T08:13:41.967

9

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

xnor

Posted 2014-01-23T19:18:03.520

Reputation: 115 687

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

– Lynn – 2016-08-09T10:27:11.860

@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. – xnor – 2016-08-10T10:14:20.757

8

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.

Laikoni

Posted 2014-01-23T19:18:03.520

Reputation: 23 676

8

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.

Laikoni

Posted 2014-01-23T19:18:03.520

Reputation: 23 676

I like: void a>void b Unfortunately, the generic version is not imported by default. :-( – Lemming – 2020-02-13T22:37:04.400

8

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])[]

xnor

Posted 2014-01-23T19:18:03.520

Reputation: 115 687

Perhaps scanl(flip(:))[] "abc" = ["","a","ba","cba"] is also worth mentioning – sometimes the prefixes being backwards doesn't matter. – Lynn – 2018-05-28T10:50:18.220

3

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

– Laikoni – 2018-12-08T17:36:46.243

7

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"

ბიმო

Posted 2014-01-23T19:18:03.520

Reputation: 15 345

1("123">>) is shorter. – Ørjan Johansen – 2018-12-19T16:23:28.947

@ØrjanJohansen: Ah damn, it was meant for educational purposes :P (showing that you can join multiple functions, not only two) – ბიმო – 2018-12-19T16:25:28.660

By my count 8−11 functions should be 4−11. (Best case if all functions need parentheses with <>.) – Ørjan Johansen – 2018-12-19T16:38:25.627

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

– ბიმო – 2018-12-19T17:25:25.087

1Oh, 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)). – Ørjan Johansen – 2018-12-19T17:37:32.730

1@Ø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 ($). – ბიმო – 2018-12-19T17:45:26.517

I think you meant Monoid a => Monoid (IO a). The second Monoid is missing. – dfeuer – 2019-03-16T05:50:54.163

@dfeuer: Yes, you're right that was a typo. Fixed it, thank you for carefully reading through it :) – ბიმო – 2019-03-16T16:42:28.070

7

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!

BlackCap

Posted 2014-01-23T19:18:03.520

Reputation: 3 576

6

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.

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

Laikoni

Posted 2014-01-23T19:18:03.520

Reputation: 23 676

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

– Zgarb – 2017-01-18T14:05:20.893

@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. – Laikoni – 2017-01-18T15:18:13.300

1@Zgarb TIO's ghc was updated to 8.0.2 thanks to Dennis. – Laikoni – 2017-01-22T20:06:11.520

TIOv2 Alpha was replaced with a fork of TIO Nexus, so GHC8.0.2 should be supported. – CalculatorFeline – 2017-06-01T15:38:20.290

6

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.

bartavelle

Posted 2014-01-23T19:18:03.520

Reputation: 1 261

2Golfier: Add a -cpp compiler flag. – Laikoni – 2017-10-31T21:22:39.490

6

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.

flawr

Posted 2014-01-23T19:18:03.520

Reputation: 40 560

6There are cases where read.show works too, if GHC can infer the types. (For example: sin$read$show someInt.) – Lynn – 2017-11-18T14:23:06.673

1toEnum :: Enum a => Int -> a also works, though slightly more constrained. – Bubbler – 2019-01-18T07:20:51.957

6

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.

Zgarb

Posted 2014-01-23T19:18:03.520

Reputation: 39 083

1Might 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. – Ørjan Johansen – 2018-01-11T19:26:01.150

6

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.

Zgarb

Posted 2014-01-23T19:18:03.520

Reputation: 39 083

1Great 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])[[]]. – xnor – 2016-11-04T07:02:28.507

When applied directly to some x this can be slightly shortened to words.concat<$>mapM(\c->[[c],c:" "])x . – Laikoni – 2017-04-24T20:44:45.707

5

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

Julian Wolf

Posted 2014-01-23T19:18:03.520

Reputation: 1 139

@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] – Julian Wolf – 2017-07-06T23:15:40.510

5

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.

  1. If you have \x -> x, replace with id
  2. If you have \x -> A, where A is any expression in which x does not occur, replace with const A
  3. If you have \x -> A x, where x does not occur in A, replace with A. This is known as "eta contraction".
  4. If you have \x -> A B, then
    1. If x occurs in both A and B, replace with (\x -> A) <*> (\x -> B).
    2. If x occurs in just A, replace with flip (\x -> A) B
    3. If x occurs in just B, replace with A . (\x -> B),
    4. 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:

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

flawr

Posted 2014-01-23T19:18:03.520

Reputation: 40 560

in the general case, (\x -> A B x) = join ((\x -> A) <*> (\x -> B)). – Will Ness – 2018-01-30T18:35:03.017

5

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

Silvio Mayolo

Posted 2014-01-23T19:18:03.520

Reputation: 1 817

3I like how plumbers calls itself *pointless plumbing combinators*. – Dennis – 2017-12-30T18:56:47.660

4

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.

Renzeee

Posted 2014-01-23T19:18:03.520

Reputation: 599

1If 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 – 2017-01-11T07:59:10.173

@Zgarb: of course, I'm always doing that when writing answers, but for this tip I totally forgot about it. – Renzeee – 2017-01-11T08:15:09.867

1The same goes for chr and toEnum, however the type of toEnum needs to be forced from context. – Laikoni – 2017-01-13T16:14:52.087

4

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

cole

Posted 2014-01-23T19:18:03.520

Reputation: 3 526

Using =<< instead of <*> gives a different parameter order that is sometimes useful. – Ørjan Johansen – 2019-07-24T10:14:48.770

1(<*>) is the S combinator; pure is the K combinator. – Esolanging Fruit – 2019-07-24T19:52:20.320

4

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

Lynn

Posted 2014-01-23T19:18:03.520

Reputation: 55 648

3

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.

totallyhuman

Posted 2014-01-23T19:18:03.520

Reputation: 15 378

5It 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 – H.PWiz – 2018-01-05T18:03:14.007

2Also the ^2 in the primality test is only needed for n==4. – Ørjan Johansen – 2018-01-05T18:37:58.090

3The 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 <$. – Ørjan Johansen – 2018-01-05T18:40:50.020

@ØrjanJohansen, some of those tests look similar to Wilson's theorem, but not the same. Where's the square come from? – dfeuer – 2019-03-14T20:46:19.893

@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. – Ørjan Johansen – 2019-03-14T22:36:27.647

3

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.

ბიმო

Posted 2014-01-23T19:18:03.520

Reputation: 15 345

3

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.

Potato44

Posted 2014-01-23T19:18:03.520

Reputation: 2 835

3

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.

dfeuer

Posted 2014-01-23T19:18:03.520

Reputation: 1 016

3

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

dfeuer

Posted 2014-01-23T19:18:03.520

Reputation: 1 016

(,)mempty popped into my mind as another example... not sure how useful. – Ørjan Johansen – 2019-03-14T23:46:22.317

Oh, and Right too. – Ørjan Johansen – 2019-03-15T03:43:02.410

3

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]

Craig Roy

Posted 2014-01-23T19:18:03.520

Reputation: 790

3

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.

proud haskeller

Posted 2014-01-23T19:18:03.520

Reputation: 5 866

1I 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 – 2016-03-27T23:16:39.240

@xnor as the code golfer, you can modify your f whatever way fits best. We're not writing library functions here. – proud haskeller – 2016-03-27T23:19:30.480

@xnor Oh, that's a way I haven't thought of! I'll add it. – proud haskeller – 2016-03-27T23:20:46.183

1Oh, 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 – 2016-03-27T23:22:34.007

@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. – proud haskeller – 2016-03-27T23:26:34.347

2

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"

cole

Posted 2014-01-23T19:18:03.520

Reputation: 3 526

1Some 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]. – Ørjan Johansen – 2019-06-29T01:57:52.053

@ØrjanJohansen nice catch on the parentheses, and yeah I’m sure there are other tricks, these were contrived examples to demonstrate the utility. – cole – 2019-06-29T02:23:21.927