Jakie masz ogólne wskazówki na temat gry w golfa w Haskell? Szukam pomysłów, które można by zastosować do problemów z golfem w kodzie, które są przynajmniej nieco specyficzne dla Haskell. Proszę zamieścić tylko jedną wskazówkę na odpowiedź.

Jeśli dopiero zaczynasz grę w golfa w Haskell, zapoznaj się z Przewodnikiem po zasadach gry w golfa w Haskell . Istnieje również dedykowany czat Haskell: Of Monads and Men .

Zdefiniuj operatory infix zamiast funkcji binarnych

To oszczędza zwykle jedną lub dwie spacje na definicję lub wywołanie.

0!(y:_)=y
x!(y:z)=(x-1)!z

vs.

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

Symbole dostępne dla operatorów 1 bajt jest !, #, %, &i ?. Wszystkie inne znaki interpunkcyjne ASCII są już zdefiniowane jako Preludium (takie jak $) lub mają specjalne znaczenie w składni Haskella (takie jak @).

Jeśli potrzebujesz więcej niż pięciu operatorów, możesz użyć kombinacji powyższych, takich jak !#niektóre znaki interpunkcyjne Unicode, takie jak te (wszystkie 2 bajty w UTF-8):

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

W razie potrzeby używaj bezcelowej (lub -free) notacji

Często funkcję z jednym lub dwoma parametrami można zapisać bez punktów.

Zatem lista krotek, których elementy są zamieniane, jest naiwnie zapisana jako:

revlookup :: Eq b => b -> [(a, b)] -> Maybe a
revlookup e l=lookup e(map swap l)

(ten typ ma na celu pomóc ci zrozumieć, co robi).

dla naszych celów jest to o wiele lepsze:

revlookup=(.map swap).lookup

Użyj listy monad

Szybki przegląd:

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

Przykłady:

• Powtarzanie listy dwa razy

  Prelude> "aa">>[1..5]
  [1,2,3,4,5,1,2,3,4,5]
  

• Krótszy concatMap

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

• Krótsze concat+ zrozumienie listy

  Prelude> do x<-[1..5];[1..x]
  [1,1,2,1,2,3,1,2,3,4,1,2,3,4,5]
  

• Produkt kartezjański

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

• Lista współrzędnych na siatce

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

Używaj osłon nie warunkowych:

f a=if a>0 then 3 else 7
g a|a>0=3|True=7

Używaj średników, a nie wcięć

f a=do
  this
  that
g a=do this;that

Użyj funkcji boolowskich dla funkcji boolowskich

f a=if zzz then True else f yyy
g a=zzz||f yyy

(SO przeszkadza mi, żebym mógł opublikować je osobno)

interact :: (String → String) → IO ()

Ludzie często zapominają, że ta funkcja istnieje - pobiera wszystkie standardowe wejścia i stosuje ją do funkcji (czystej). Często widzę main-code wzdłuż linii

main=getContents>>=print.foo

podczas

main=interact$show.foo

jest nieco krótszy. Jest w Preludium, więc nie ma potrzeby importowania!

Użyj GHC 7.10

Pierwsza wersja GHC zawierająca te rzeczy została wydana 27 marca 2015 r .

Jest to najnowsza wersja, a Prelude ma kilka nowych dodatków, które są przydatne do gry w golfa:

(<$>)I (<*>)operatorzy

Przydali się ci przydatni operatorzy Data.Applicative! <$>jest po prostu fmap, więc można zastąpić map f xi fmap f xze f<$>xwszędzie i odzyskać bajtów. Jest także <*>przydatny w Applicativeprzypadku list:

Prelude> (,)<$>[1..2]<*>"abcd"
[(1,'a'),(1,'b'),(1,'c'),(1,'d'),(2,'a'),(2,'b'),(2,'c'),(2,'d')]

(<$)operatora

x<$ajest równoważne z fmap (const x) a; tzn. zamień każdy element w pojemniku na x.

Jest to często miła alternatywa dla replicate: 4<$[1..n]jest krótsza niż replicate n 4.

Propozycja składana / przejezdna

Następujące funkcje zostały przeniesione z pracy na listach [a]do ogólnych Foldabletypów t a:

fold*, null, length, elem, maximum, minimum, sum, product
and, or, any, all, concat, concatMap

Oznacza to, że teraz pracują również Maybe atam, gdzie zachowują się jak „listy zawierające co najwyżej jeden element”. Na przykład null Nothing == True, lub sum (Just 3) == 3. Podobnie lengthzwraca 0 dla Nothingi 1 dla Justwartości. Zamiast pisać x==Just ymożesz pisać elem y x.

Możesz także zastosować je na krotkach, co działa tak, jakbyś zadzwonił jako \(a, b) -> [b]pierwszy. Jest prawie całkowicie bezużyteczny, ale or :: (a, Bool) -> Booljest o jedną postać krótszy niż sndi elem bjest krótszy niż (==b).snd.

Funkcje Monoid memptyimappend

Nie często ratuje życie, ale jeśli możesz wywnioskować, jaki memptyjest typ, jest on o jeden bajt krótszy niż Nothing, więc jest taki.

Użyj 1<2zamiast Truei 1>2zamiast False.

g x|x<10=10|True=x
f x|x<10=10|1<2=x

Używaj wyrażeń listowych (w sprytny sposób)

Wszyscy wiedzą, że są użyteczną składnią, często krótszą niż map+ lambda:

Prelude> [[1..x]>>show x|x<-[1..9]]
["1","22","333","4444","55555","666666","7777777","88888888","999999999"]

Lub filter(i opcjonalnie mapw tym samym czasie):

Prelude> [show x|x<-[1..60],mod 60x<1]
["1","2","3","4","5","6","10","12","15","20","30","60"]

Ale od czasu do czasu przydają się dziwniejsze zastosowania. Po pierwsze, lista nie musi zawierać żadnych <-strzałek:

Prelude> [1|False]
[]
Prelude> [1|True]
[1]

Co oznacza if p then[x]else[], że możesz pisać [x|p]. Ponadto, aby policzyć liczbę elementów listy spełniających warunek, intuicyjnie napisałbyś:

length$filter p x

Ale to jest krótsze:

sum[1|y<-x,p y]

Znać twój Prelude

Odpal GHCi i przewiń dokumentację Preludium . Za każdym razem, gdy przechodzisz przez funkcję o krótkiej nazwie, warto zwrócić uwagę na niektóre przypadki, w których może być przydatna.

Na przykład, załóżmy, że chcesz, aby przekształcić ciąg s = "abc\ndef\nghi"w jedno miejsce, które jest oddzielone, "abc def ghi". Oczywistym sposobem jest:

unwords$lines s

Ale możesz zrobić lepiej, jeśli nadużyjesz max, a fakt, że \n < space < printable ASCII:

max ' '<$>s

Innym przykładem jest lex :: String -> [(String, String)]coś tajemniczego:

Prelude> lex "   some string of Haskell tokens  123  "
[("some"," string of Haskell tokens  123  ")]

Spróbuj fst=<<lex suzyskać pierwszy token z ciągu, pomijając białe znaki. Tutaj jest rozwiązanie przez henkma mądry, który używa lex.showna Rationalwartości.

Dopasuj stałą wartość

Zrozumienie listy może dopasowywać wzór na stałe.

[0|0<-l]

To wyodrębnia zera z listy l, tzn. Tworzy listę tylu zer, ile jest l.

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

To tworzy listę tylu 1, ile jest elementów, lktóre fprzechodzą na pustą listę (używając <$>jako infix map). Zastosuj, sumaby policzyć te elementy.

Porównać:

[1|[]<-f<$>l]
[1|x<-l,f x==[]]

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

Stała może być używana jako część dopasowania wzorca. To wyodrębnia drugie wpisy ze wszystkich krotek, których pierwszym wpisem jest 0.

Zauważ, że wszystkie z nich wymagają rzeczywistego stałego literału, a nie wartości zmiennej. Na przykład let x=1 in [1|x<-[1,2,3]]wyświetli [1,1,1], a nie [1], ponieważ zewnętrzne xwiązanie zostanie zastąpione.

Użyj wordszamiast długiej listy ciągów. To nie jest tak naprawdę specyficzne dla Haskell, inne języki też mają podobne sztuczki.

["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

Poznaj swoje funkcje monadyczne

1)
symulować funkcje monadyczne za pomocą mapM.

kod będzie miał wiele razy sequence(map f xs), ale można go zastąpić mapM f xs. nawet gdy używa się sequencego sam, jest to dłuższe mapM id.

2)
łącz funkcje za pomocą (>>=)(lub (=<<))

wersja monad funkcji (>>=)jest zdefiniowana w następujący sposób:

(f >>= g) x = g (f x) x 

może być przydatny do tworzenia funkcji, których nie można wyrazić jako potok. na przykład \x->x==nub xjest dłuższy niż nub>>=(==)i \t->zip(tail t)tjest dłuższy niż tail>>=zip.

Argumenty mogą być krótsze niż definicje

Właśnie zostałem bardzo ciekawie wyrzucony przez henkma .

Jeśli funkcja pomocnicza fw Twojej odpowiedzi używa operatora, który nie jest używany w innym miejscu w Twojej odpowiedzi i fjest wywoływany jeden raz, uczyń go argumentem f.

To:

(!)=take
f a=5!a++3!a
reverse.f

Czy dwa bajty są dłuższe niż to:

f(!)a=5!a++3!a
reverse.f take

Użyj operatora minus (:)

podczas łączenia list, jeśli pierwszy ma długość 1, użyj :zamiast niego.

a++" "++b
a++' ':b  -- one character shorter

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

Nie używaj backsick zbyt często. Backticks to fajne narzędzie do tworzenia sekcji funkcji prefiksów, ale czasami może być niewłaściwie używane.

Kiedyś widziałem, jak ktoś pisze to podwyrażenie:

(x`v`)

Chociaż jest tak samo jak tylko v x.

Innym przykładem jest pisanie (x+1)`div`y w przeciwieństwie do div(x+1)y.

Widzę to się stało dookoła divi elemczęściej, ponieważ funkcje te są zwykle używane jako wrostkiem w regularnych kodu.

Użyj strażników wzorów

Są krótsze niż a letlub lambda, które dekonstruują argumenty funkcji, którą definiujesz. To pomaga, gdy trzeba coś podobnego fromJustz Data.Maybe:

f x=let Just c=… in c

jest dłuższy niż

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

jest dłuższy niż

m(Just c)=c;f x=m$…

jest dłuższy niż

f x|Just c<-…=c

W rzeczywistości są krótsze, nawet jeśli wiążą zwykłą starą wartość zamiast dekonstruować: patrz wskazówka xnor .

Krótszy warunkowy

last$x:[y|b]

jest równa

if b then y else x

Oto jak to działa:

             [y|b]   x:[y|b]   last$x:[y|b]
if...      +--------------------------------
b == False | []      [x]       x
b == True  | [y]     [x,y]     y

Praca ze znakiem minus

Znak minus -jest irytującym wyjątkiem od wielu reguł składniowych. Ta wskazówka zawiera kilka krótkich sposobów wyrażania negacji i odejmowania w Haskell. Daj mi znać, jeśli coś przeoczyłem.

Negacja

• Aby zanegować wyrażenie e, po prostu zrób -e. Na przykład -length[1,2]daje -2.
• Jeśli ejest nawet umiarkowanie skomplikowany, będziesz potrzebować nawiasów e, ale zwykle możesz zaoszczędzić bajt, przesuwając je: -length(take 3 x)jest krótszy niż -(length$take 3 x).
• Jeśli ejest poprzedzony przez =lub operator poprawek o trwałości mniejszej niż 6, potrzebujesz spacji: f= -2określa fi k< -2sprawdza, czy kjest mniejsza niż -2. Jeśli trwałość wynosi 6 lub więcej, potrzebujesz parens: 2^^(-2)daje 0.25. Zwykle możesz zmienić układ rzeczy, aby się ich pozbyć: na przykład rób -k>2zamiast k< -2.
• Podobnie, jeśli !jest operatorem, to -a!bjest analizowane tak, (-a)!bjakby poprawność !wynosi co najwyżej 6 ( -1<1daje to True), a -(a!b)poza tym ( -[1,2]!!0daje -1). Domyślna poprawność zdefiniowanych przez użytkownika operatorów i funkcji zaznaczania wstecznego wynosi 9, więc są zgodne z drugą zasadą.
• Aby zamienić negację w funkcję (do użycia z mapitp.), Skorzystaj z sekcji (0-).

Odejmowanie

• Aby uzyskać funkcję odejmującą k, użyj sekcji (-k+), która dodaje -k. kmoże być nawet dość złożonym wyrażeniem: (-2*length x+)działa zgodnie z oczekiwaniami.
• Aby odjąć 1, użyj predzamiast tego, chyba że wymagałoby to spacji po obu stronach. Jest to rzadkie i zwykle dzieje się z untilfunkcją zdefiniowaną przez użytkownika lub, ponieważ map pred xmoże być zastąpione przez pred<$>xi iterate pred xprzez [x,x-1..]. A jeśli masz f pred xgdzieś, prawdopodobnie i ftak powinieneś zdefiniować funkcję infix. Zobacz tę wskazówkę .

Spróbuj zmienić definicje funkcji i / lub argumentów

Czasami można zapisać kilka bajtów, zmieniając kolejność dopasowywania wzorców w definicji funkcji. Oszczędności te są tanie, ale łatwe do przeoczenia.

Jako przykład rozważ następującą wcześniejszą wersję (części) tej odpowiedzi :

(g?x)[]=x
(g?x)(a:b)=g(g?x$b)a

Jest to rekurencyjna definicja ?, przy czym podstawowym przypadkiem jest pusta lista. Ponieważ []nie jest to przydatna wartość, powinniśmy zamienić definicje i zastąpić je _znakiem zastępczym lub fikcyjnym argumentem y, zapisując bajt:

(g?x)(a:b)=g(g?x$b)a
(g?x)y=x

Na podstawie tej samej odpowiedzi rozważ tę definicję:

f#[]=[]
f#(a:b)=f a:f#b

Pusta lista występuje w wartości zwracanej, dzięki czemu możemy zapisać dwa bajty, zamieniając przypadki:

f#(a:b)=f a:f#b
f#x=x

Również kolejność argumentów funkcji może czasem mieć znaczenie, umożliwiając usunięcie niepotrzebnych białych znaków. Rozważ wcześniejszą wersję tej odpowiedzi :

h p q a|a>z=0:h p(q+2)(a-1%q)|1<2=1:h(p+2)q(a+1%p)

Jest przykry kawał spacji pomiędzy hi pw pierwszej gałęzi. Możemy się go pozbyć, definiując h a p qzamiast 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

Nie marnuj strażnika „inaczej”

Ostateczna osłona, która jest funkcją catch-all True(krótsza jako 1>0), może zostać użyta do powiązania zmiennej. Porównać:

... |1>0=1/(x+y)
... |z<-x+y=1/z

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

Ponieważ strażnik jest obowiązkowy i w inny sposób zmarnowany, niewiele potrzeba, aby było warto. Wystarczy zapisać parę parenów lub powiązać wyrażenie długości 3, które jest używane dwukrotnie. Czasami możesz zanegować strażników, aby ostatecznym przypadkiem było wyrażenie, które najlepiej używa wiązania.

Użyj ,zamiast &&w osłonach

Wiele warunków w osłonie, które wszyscy muszą trzymać, można łączyć ,zamiast &&.

f a b | a/=5 && b/=7 = ...
f a b | a/=5 ,  b/=7 = ...

Krótsza składnia lokalnych deklaracji

Czasami musisz zdefiniować lokalną funkcję lub operator, ale kosztuje to wiele bajtów do napisania wherelub let…inpodniesienia do najwyższego poziomu poprzez dodanie dodatkowych argumentów.

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

Na szczęście Haskell ma mylącą i rzadko używaną, ale dość zwięzłą składnię dla lokalnych deklaracji :

fun1 pattern1 | let fun2 pattern2 = expr2 = expr1

W tym przypadku:

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

Możesz użyć tej składni z deklaracjami złożonymi z wielu instrukcji lub z wieloma deklaracjami, a nawet zagnieżdża:

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

Działa również w przypadku wiązania zmiennych lub innych wzorców, chociaż osłony wzorców są do tego krótsze, chyba że masz również funkcje wiązania.

Uniknąć 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..]

Każde z tych czterech wyrażeń spowoduje utworzenie nieskończonej listy n.

To bardzo konkretna wskazówka, ale może zaoszczędzić do 3 bajtów!

Krótsze warunki warunkowe, gdy jednym wynikiem jest pusta lista

Gdy potrzebujesz warunku, który zwraca listę Alub pustą listę w []zależności od niektórych warunków C, wówczas istnieje kilka krótszych alternatyw dla zwykłych konstrukcji warunkowych:

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

Przykłady: 1 , 2

Zasady analizy lambda

Wyrażenie lambda tak naprawdę nie potrzebuje nawiasów wokół niego - po prostu łapczywie chwyta wszystko, więc całość wciąż się analizuje, np.

• zamykający paren - (foo$ \x -> succ x)
• w - let a = \x -> succ x in a 4
• koniec linii - main = getContents>>= \x -> head $ words x
• itp..

napotkano i istnieją dziwne przypadki, w których można zaoszczędzić bajt lub dwa. Sądzę, że \można go również użyć do zdefiniowania operatorów, więc podczas korzystania z tego będziesz potrzebował spacji, pisząc lambda bezpośrednio za operatorem (jak w trzecim przykładzie).

Oto przykład, w którym użycie lambda było najkrótszą rzeczą, jaką mogłem wymyślić. Kod zasadniczo wygląda następująco:

a%f=...
f t=sortBy(% \c->...)['A'..'Z']

Zamień letna lambda

Zwykle może to skrócić pojedynczą definicję pomocniczą, która z jakiegoś powodu nie może być związana ze strażnikiem ani zdefiniowana globalnie. Na przykład zamień

let c=foo a in bar

o 3 bajty krótsze

(\c->bar)$foo a

W przypadku wielu definicji pomocniczych wzmocnienie jest prawdopodobnie mniejsze, w zależności od liczby definicji.

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

Jeśli niektóre definicje odnoszą się do innych, jeszcze trudniej jest zapisać bajty w ten sposób:

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

Głównym zastrzeżeniem jest to, że letpozwala definiować zmienne polimorficzne, ale lambdy nie, jak zauważają @ChristianSievers. Na przykład,

let f=length in(f["True"],f[True])

powoduje (1,1), ale

(\f->(f["True"],f[True]))length

daje błąd typu.

Powiąż za pomocą strażników

Podczas definiowania nazwanej funkcji można powiązać wyrażenie ze zmienną w osłonie. Na przykład,

f s|w<-words s=...

robi to samo co

f s=let w=words s in ...
f s=(\w->...)$words s

Użyj tego, aby zaoszczędzić na powtarzanych wyrażeniach. Gdy wyrażenie jest używane dwukrotnie, łamie się ono nawet przy długości 6, chociaż problemy z odstępami i pierwszeństwem mogą to zmienić.

(W tym przykładzie, jeśli pierwotna zmienna snie jest używana, jest to krótsze

g w=...
f=g.words

ale nie dotyczy to wiązania bardziej złożonych wyrażeń).

Użyj (0<$)zamiast lengthdo porównań

Podczas testowania, czy lista ajest dłuższa niż lista b, zwykle pisze się

length a>length b

Jednak zastąpienie każdego elementu obu list tą samą wartością, np. 0A następnie porównanie tych dwóch list może być krótsze:

(0<$a)>(0<$b)

Wypróbuj online!

Nawias są potrzebne, bo <$i operatorów porównania ( ==, >, <=, ...) mają ten sam poziom pierwszeństwo 4, chociaż w niektórych innych przypadkach może nie być potrzebne, oszczędzając nawet więcej bajtów.

Krótszy transpose

Aby skorzystać z transposefunkcji Data.List, należy ją zaimportować. Jeśli jest to jedyna funkcja wymagająca importu, można zapisać bajt, stosując następującą foldrdefinicję transpose:

import Data.List;transpose
e=[]:e;foldr(zipWith(:))e

Zauważ, że zachowanie jest identyczne tylko dla listy list o tej samej długości.

Z powodzeniem wykorzystałem to tutaj .

Uzyskaj sufiksy

Użyj, scanr(:)[]aby uzyskać sufiksy listy:

λ scanr(:)[] "abc"
["abc","bc","c",""]

To jest znacznie krótsze niż tailspóźniej import Data.List. Możesz zrobić prefiksy z scanr(\_->init)=<<id(znalezione przez Ørjan Johansen).

λ  scanr(\_->init)=<<id $ "abc"
["","a","ab","abc"]

To oszczędza bajt

scanl(\s c->s++[c])[]