Haskell

Dokumentacja Scalaz często odwołuje się do bibliotek lub artykułów używających Haskella jako języka programowania. W tym krótkim rozdziale poznamy jego podstawy, tak, aby móc zrozumieć wspomniane materiały oraz móc uczestniczyć w Haskellowych prezentacjach na konferencjach o programowaniu funkcyjnym.

Dane

Haskell ma bardzo schludną składnię dla ADT. Oto tradycyjna lista:

  data List a = Nil | Cons a (List a)

List jest konstruktorem typu, a to parametr typu, a | rozdziela konstruktory danych, które w tym wypadku to: Nil czyli pusta lista oraz Cons czyli komórka listy. Cons przyjmuje dwa parametry, które są rozdzielone białym znakiem. Nie ma tu przecinków ani nawiasów.

W Haskellu nie ma też podtypowania, więc nie ma czegoś takiego jak typ Nil lub Cons, oba tworzą typ List.

Przybliżone tłumaczenie na Scalę:

  sealed abstract class List[A]
  object Nil {
    def apply[A]: List[A] = ...
    def unapply[A](as: List[A]): Option[Unit] = ...
  }
  object Cons {
    def apply[A](head: A, tail: List[A]): List[A] = ...
    def unapply[A](as: List[A]): Option[(A, List[A])] = ...
  }

A więc, konstruktor typu to odpowiednik sealed abstract class a każdy z konstruktorów danych to para .apply/.unapply. Warto zauważyć, że przy takim kodowaniu Scala nie jest w stanie sprawdzić czy pattern matching jest wyczerpujący, i dlatego też nie jest ono używane w Scalaz.

Możemy też użyć infiksu, tworząc ładniejszą definicję z :. zamiast Cons

  data List t = Nil | t :. List t
  infixr 5 :.

Specyfikujemy tutaj fixity, które może przyjąć jedną z wartości infix, infixl lub infixr, które oznaczają odpowiednio brak łączności, łączność lewostronną i prawostronną. Liczby od 0 do 9 określają priorytet operacji. Możemy teraz stworzyć listę liczb całkowitych za pomocą

  1 :. 2 :. Nil

Haskell posiada już definicję listy i jest ona na tyle ważna dla programowania funkcyjnego, że zasłużyła na osobną składnię zdefiniowaną na poziomie języka: [a].

  data [] a = [] | a : [a]
  infixr 5 :

oraz wygodny wielowartościowy konstruktor [1, 2, 3] zamiast 1 : 2 : 3 : [].

Koniec końców nasze ADT musi przechowywać wartości prymitywne. Najpopularniejsze z nich to:

  • Char - znak unikodu
  • Text - blok tekstu opartego o unikod
  • Int - zależna od sprzętu liczba całkowita ze znakiem o stałej precyzji
  • Word - liczba całkowita bez znaku z wariantami o stałym rozmiarze Word8 / Word16 / Word32 / Word64
  • Float / Double - liczby zmiennoprzecinkowe o pojedynczej i podwójnej precyzji, zgodne z IEEE
  • Integer / Natural - liczba całkowita o arbitralnej precyzji. Ze znakiem oraz dodatnia.
  • (,) - tuple o rozmiarach od 0 do 62
  • IO - inspiracja dla IO w Scalaz, implementowana na poziomie środowiska uruchomieniowego

z honorowym miejscem dla

  data Bool       = True | False
  data Maybe a    = Nothing | Just a
  data Either a b = Left a  | Right b
  data Ordering   = LT | EQ | GT

Haskell, podobnie jak Scala, pozwala na definiowanie aliasów typów. Alias i jego rozwiniętą forma mogą być używane zamiennie. Z powodów historycznych String zdefiniowany jest alias na listę Charów

  type String = [Char]

co jest reprezentacją bardzo niewydajną i dlatego właśnie powinniśmy używać typu Text.

Możemy też definiować nazwy pól w ADT używając składni rekordów, co oznacza umieszczenie konstruktorów danych w klamrach i dodanie do pól anotacji typów za podwójnym dwukropkiem aby określić ich typ.

  -- raw ADT
  data Resource = Human Int String
  data Company  = Company String [Resource]
  
  -- with record syntax
  data Resource = Human
                  { serial    :: Int
                  , humanName :: String
                  }
  data Company  = Company
                  { companyName :: String
                  , employees   :: [Resource]
                  }

Zauważ, że konstruktor danych Human i typ Resource nie muszą mieć tej samej nazwy. Rekordy generują dla nas metody pozwalające na dostęp do pól i łatwe kopiowanie danych.

  -- construct
  adam = Human 0 Adam
  -- field access
  serial adam
  -- copy
  eve = adam { humanName = "Eve" }

Bardziej wydajną alternatywą dla pojedynczych definicji danych jest użycie słowa kluczowego newtype, które nie niesie ze sobą żadnego narzutu wydajnościowego:

  newtype Alpha = Alpha { underlying :: Double }

Jest to odpowiednik extends AnyVal, tyle że bez żadnych haczyków.

Funkcje

Mimo że nie jest to konieczne, to dobrą praktyką jest opatrywanie funkcji sygnaturami typu, co wyrażane jest jako nazwa funkcji za którą podąża jej typ. Dla przykładu, oto foldl wyspecjalizowany dla listy

  foldl :: (b -> a -> b) -> b -> [a] -> b

Wszystkie funkcje w Haskellu są domyślnie rozwinięte (curried), parametry rozdzielone są `->, a ostatni typ to typ zwracany przez funkcję. Powyższy przykład to odpowiednik Scalowej sygnatury

  def foldLeft[A, B](f: (B, A) => B)(b: B)(as: List[A]): B

Tyle, że:

  • bez słów kluczowych
  • bez deklaracji typów które wyprowadzamy
  • bez nazywania parametrów

Wszystko to sprawia, że kod jest bardziej zwięzły.

Funkcje infiksowe definiowane są w nawiasach i wymagają określenia fixity:

  (++) :: [a] -> [a] -> [a]
  infixr 5 ++

Zwykłe funkcje mogą być wołane w pozycji infiksowej poprzez otoczenie nazwy apostrofami, a infiksowe możemy wywoływać tak jak normalne jeśli pozostawimy nawiasy wokół nazwy. Poniższe wywołania są równoznaczne:

  a `foo` b
  foo a b

Funkcja infiksowa może być rozwinięta z lewej bądź prawej strony, często dając różną semantykę:

  invert = (1.0 /)
  half   = (/ 2.0)

Funkcje zazwyczaj pisane są tak, aby najbardziej ogólny parametr był na początku, co pozwala zmaksymalizować reużywalność domyślnej rozwiniętej formy.

Definicje funkcji mogą używać dopasowywania wzorców z jedną linią na wariant. W tym miejscu możemy nazwać nasze parametry używając konstruktorów danych do ich wyekstrahowania, podobnie jak w Scalowej klauzuli case:

  fmap :: (a -> b) -> Maybe a -> Maybe b
  fmap f (Just a) = Just (f a)
  fmap _ Nothing  = Nothing

Podkreślenie służy do ignorowania nieistotnych parametrów. Nazwy funkcji mogą występować w pozycji infiksowej również w definicjach:

  (<+>) :: Maybe a -> Maybe a -> Maybe a
  Just a <+> _      = Just a
  Empty  <+> Just a = Just a
  Empty  <+> Empty  = Empty

Funkcje anonimowe (lambdy) definiujemy z pomocą odwrotnego ukośnika, co przypomina grecką literę λ. Poniższe definicje są równoznaczne:

  (*)
  (\a1 -> \a2 -> a1 * a2)
  (\a1 a2     -> a1 * a2)

Funkcje używające dopasowań w Haskellu to tak naprawdę jedynie syntax sugar ponad zagnieżdżonymi lambdami. Rozważmy prostą funkcję, która tworzy tuple z 3 argumentów:

  tuple :: a -> b -> c -> (a, b, c)

Jej implementacja

  tuple a b c = (a, b, c)

jest rozwijana przez kompilator do 

  tuple = \a -> \b -> \c -> (a, b, c)

W ciele funkcji możemy tworzyć lokalne przypisania za pomocą klauzul let i where. Poniższe definicje map dla listy są równoznaczne (apostrof jest poprawnym identyfikatorem):

  map :: (a -> b) -> [a] -> [b]
  
  -- explicit
  map f as = foldr map' [] as
             where map' a bs = f a : bs
  
  -- terser, making use of currying
  map f    = foldr map' []
             where map' a = (f a :)
  
  -- let binding
  map f    = let map' a = (f a :)
             in foldr map' []
  
  -- actual implementation
  map _ []       = []
  map f (x : xs) = f x : map f xs

if / then / else to słowa kluczowe do definiowania wyrażeń warunkowych:

  filter :: (a -> Bool) -> [a] -> [a]
  filter _ [] = []
  filter f (head : tail) = if f head
                           then head : filter f tail
                           else filter f tail

Alternatywnie możemy użyć ograniczeń wariantów (case guards)

  filter f (head : tail) | f head    = head : filter f tail
                         | otherwise = filter f tail

Dopasowania dla dowolnego wyrażenia definiujemy używają case ... of

  unfoldr :: (a -> Maybe (b, a)) -> a -> [b]
  unfoldr f b = case f b of
                  Just (b', a') -> b' : unfoldr f a'
                  Nothing       -> []

Ograniczenia mogą być używane wewnątrz dopasowań. Możemy, na przykład, chcieć potraktować zera w specjalny sposób:

  unfoldrInt :: (a -> Maybe (Int, a)) -> a -> [Int]
  unfoldrInt f b = case f b of
                     Just (i, a') | i == 0    -> unfoldrInt f a'
                                  | otherwise -> i : unfoldrInt f a'
                     Nothing                  -> []

Na koniec dwie funkcje warte wspomnienia: ($) i (.)

  -- application operator
  ($) :: (a -> b) -> a -> b
  infixr 0
  
  -- function composition
  (.) :: (b -> c) -> (a -> b) -> a -> c
  infixr 9

Obie są stylistycznymi alternatywami dla zagnieżdżonych nawiasów.

Poniższe wywołania są równoznaczne

  Just (f a)
  Just $ f a

tak jak i

  putStrLn (show (1 + 1))
  putStrLn $ show $ 1 + 1

Składanie funkcji za pomocą . jest przez wielu preferowane ponad wielokrotne użycie $

  (putStrLn . show) $ 1 + 1

Typeklasy

Aby zdefiniować typeklasę używamy słowa kluczowego class, za którym podąża jej nazwa oraz parametry typu, a wymagane metody trafiają do klauzuli where. Jeśli między typeklasami istnieje zależność, jak np. w przypadku Applicative i Functor, to może być ona wyrażona za pomocą notacji =>

  class Functor f where
    (<$>) :: (a -> b) -> f a -> f b
    infixl 4 <$>
  
  class Functor f => Applicative f where
    pure  :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b
    infixl 4 <*>
  
  class Applicative f => Monad f where
    (=<<) :: (a -> f b) -> f a -> f b
    infixr 1 =<<

Implementację danej typeklasy możemy dostarczyć za pomocą słowa kluczowego instance. Jeśli chcielibyśmy powtórzyć sygnatury metod, co dodaje nieco czytelności, musimy włączyć rozszerzenie języka InstanceSigs.

  {-# LANGUAGE InstanceSigs #-}
  
  data List a = Nil | a :. List a
  
  -- defined elsewhere
  (++) :: List a -> List a -> List a
  map :: (a -> b) -> List a -> List b
  flatMap :: (a -> List b) -> List a -> List b
  foldLeft :: (b -> a -> b) -> b -> List a -> b
  
  instance Functor List where
    (<$>) :: (a -> b) -> List a -> List b
    f <$> as = map f as
  
  instance Applicative List where
    pure a = a :. Nil
  
    Nil <*> _  = Nil
    fs  <*> as = foldLeft (++) Nil $ (<$> as) <$> fs
  
  instance Monad List where
    f =<< list = flatMap f list

Gdy chcemy skorzystać z typeklasy w funkcji, deklarujemy to za pomocą =>. Możemy na przykład zdefiniować odpowiednik Apply.apply2 ze Scalaz

  apply2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
  apply2 f fa fb = f <$> fa <*> fb

Skoro wprowadziliśmy już typeklasę Monad to jest to dobry moment na omówienie notacji do, która była inspiracją dla Scalowej konstrukcji for:

  do
    a <- f
    b <- g
    c <- h
    pure (a, b, c)

Powyższy kod rozwijany jest do

  f >>= \a ->
    g >>= \b ->
      h >>= \c ->
        pure (a, b, c)

gdzie >>= to =<< z parametrami zamienionymi miejscami

  (>>=) :: Monad f => f a -> (a -> f b) -> f b
  (>>=) = flip (=<<)
  infixl 1 >>=
  
  -- from the stdlib
  flip :: (a -> b -> c) -> b -> a -> c

a return to synonim do pure.

W przeciwieństwie do Scali, nie musimy przypisywać pustych wartości ani używać yield gdy zwracamy ().

  for {
    _ <- putStr("hello")
    _ <- putStr(" world")
  } yield ()

jest odpowiednikiem

  do putStr "hello"
     putStr " world"

Niemonadyczne wartości mogą być przypisywane z użyciem słowa kluczowego let:

  nameReturn :: IO String
  nameReturn = do putStr "What is your first name? "
                  first <- getLine
                  putStr "And your last name? "
                  last  <- getLine
                  let full = first ++ " " ++ last
                  putStrLn ("Pleased to meet you, " ++ full ++ "!")
                  pure full

Na koniec, Haskell pozwala na derywację typeklas za pomocą słowa kluczowego deriving, a mechanizm ten był inspiracją dla poznanego przez nas @scalaz.deriving. Definiowanie zasad derywacji to dość zaawansowany temat, ale sama derywacja dla ADT jest bardzo prosta:

  data List a = Nil | a :. List a
                deriving (Eq, Ord)

Algebras

In Scala, typeclasses and algebras are both defined as a trait interface. Typeclasses are injected by the implicit feature and algebras are passed as explicit parameters. There is no language-level support in Haskell for algebras: they are just data!

Consider the simple Console algebra from the introduction. We can rewrite it into Haskell as a record of functions:

  data Console m = Console
                    { println :: Text -> m ()
                    , readln  :: m Text
                    }

with business logic using a Monad constraint

  echo :: (Monad m) => Console m -> m ()
  echo c = do line <- readln c
              println c line

A production implementation of Console would likely have type Console IO. The Scalaz liftIO function is inspired by a Haskell function of the same name and can lift Console IO into any Advanced Monad stack.

Two additional language extensions make the business logic even cleaner. For example, RecordWildCards allows us to import all the fields of a data type by using {..}:

  echo :: (Monad m) => Console m -> m ()
  echo Console{..} = do line <- readln
                        println line

NamedFieldPuns requires each imported field to be listed explicitly, which is more boilerplate but makes the code easier to read:

  echo :: (Monad m) => Console m -> m ()
  echo Console{readln, println} = do line <- readln
                                     println line

Whereas in Scala this encoding may be called Finally Tagless, in Haskell it is known as MTL style. Without going into details, some Scala developers didn’t understand a research paper about the performance benefits of Generalised ADTs in Haskell.

An alternative to MTL style are Extensible Effects, also known as Free Monad style.

Moduły

Kod źródłowy napisany w Haskellu układa się w hierarchiczne moduły, a kod każdego z nich musi być zawarty z jednym pliku. Pierwsza linia w pliku określa jego nazwę

  module Silly.Tree where

Kod organizowany jest według konwencji za pomocą katalogów, tak więc plik ten znajdzie się w Silly/Tree.hs.

Domyślnie wszystkie symbole w pliku są eksportowane, ale możemy kontrolować to zachowanie. Dla przykładu wyeksportujmy typ Tree wraz z konstruktorami danych i funkcje fringe, a ominiemy funkcję sapling:

  module Silly.Tree (Tree(..), fringe) where
  
  data Tree a = Leaf a | Branch (Tree a) (Tree a)
  
  fringe :: Tree a -> [a]
  fringe (Leaf x)            = [x]
  fringe (Branch left right) = fringe left ++ fringe right
  
  sapling :: Tree String
  sapling = Leaf ""

Co ciekawe, możemy eksportować symbole, które są zaimportowane z zewnątrz. Pozwala to autorom bibliotek spakować całe API do jednego modułu niezależnie od tego jak zostało zaimplementowane.

W innym pliku możemy zaimportować wcześniej zdefiniowane Silly.Tree.

  import Silly.Tree

co jest równoznaczne ze Scalowym import silly.tree._. Jeśli chcielibyśmy ograniczyć symbole, które są importowane to wystarczy wymienić je w nawiasach zaraz za nazwą importowanego modułu:

  import Silly.Tree (Tree, fringe)

Tutaj importujemy jedynie kontruktor typu Tree (bez konstruktorów danych) i funkcję fringe. Jeśli chcielibyśmy zaimportować wszystkie konstruktory danych możemy użyć Tree(..). Jeśli potrzebujemy jedynie Branch to wystarczy to zadeklarować:

Here we only import the Tree type constructor (not the data constructors) and the fringe function. If we want to import all the data constructors (and pattern matchers) we can use Tree(..). If we only want to import the Branch constructor we can list it explicitly:

  import Silly.Tree (Tree(Branch), fringe)

Jeśli okaże się że nazwy importowanych symboli kolidują ze sobą możemy rozwiązać ten problem używając importu kwalifikowanego (qualified) z opcjonalną listą importowanych symboli

  import qualified Silly.Tree (fringe)

Teraz by wywołać fringe musimy posłużyć się identyfikatorem Silly.Tree.fringe zamiast zwykłego fringe. Podczas importowania możemy też zmienić nazwę modułu

  import qualified Silly.Tree as T

tym samym fringe jest teraz dostępne jakoT.fringe.

Alternatywnie, zamiast deklarować importowane symbole możemy wybrać to czego nie chcemy importować

  import Silly.Tree hiding (fringe)

Domyślnie moduł Prelude jest niejawnie importowany, ale jeśli zaimportujemy go wprost, to tylko nasza wersja będzie użyta. Możemy użyć tego triku aby ukryć niebezpieczne funkcje

  import Prelude hiding ((!!), head)

Możemy też całkowicie się go pozbyć za pomocą rozszerzenia języka NoImplicitPrelude.

Ewaluacja

Haskell kompiluje się do kodu natywnego, nie ma więc maszyny wirtualnej, ale nadal jest garbage collector. Podstawową właściwością Haskellowego środowiska uruchomieniowego, jest to, że wszystkie parametry są domyślnie leniwie ewaluowane. Wyrażenia traktowane są jako “thunki”, czyli obietnice dostarczenia wartości gdy będzie ona potrzebna. Thunki są redukowane tylko gdy jest to absolutnie niezbędne do kontynuowania obliczeń.

Dużą zaletą leniwej ewaluacji jest to, że zdecydowanie trudniej jest przepełnić stos! Wadą jest nieuchronny narzut wydajnościowy, dlatego też Haskell pozwala nam przełączyć się na ścisłą ewaluację dla wybranych przez nas parametrów.

Nie jest też takie oczywiste co tak na prawdę oznacza ścisła ewaluacja. Określa się, że wyrażenie jest w słabej czołowej postaci normalnej (WHNF, weak head normal form) jeśli najbardziej zewnętrzne bloki nie mogą być bardziej zredukowane, oraz w postaci normalnej jeśli wyrażenie jest w pełni wyewaluowane. Domyślna strategia ewaluacji w Scali odpowiada właśnie postaci normalnej.

Dla przykładu, te wyrażenia są w postaci normalnej:

  42
  (2, "foo")
  \x -> x + 1

natomiast poniższe nie są (mogą być dalej redukowane):

  1 + 2            -- reduces to 3
  (\x -> x + 1) 2  -- reduces to 3
  "foo" ++ "bar"   -- reduces to "foobar"
  (1 + 1, "foo")   -- reduces to (2, "foo")

Następujące wyrażenia są w WHNF ponieważ zewnętrzny kod nie może być zredukowany (mimo że części wewnętrzne mogą):

  (1 + 1, "foo")
  \x -> 2 + 2
  'f' : ("oo" ++ "bar")

a te wyrażenia już w WHNF nie są

  1 + 1              -- reduces to 2
  (\x y -> x + y) 2  -- reduces to \y -> 2 + y
  "foo" ++ "bar"     -- reduces to "foobar"

Domyślną strategią ewaluacji jest niewykonywanie żadnych redukcji gdy wyrażenie przekazywane jest jako parametr. Wsparcie na poziomie języka pozwala nam wymusić WHNF dla dowolnego wyrażenia za pomocą ($!)

  -- evaluates `a` to WHNF, then calls the function with that value
  ($!) :: (a -> b) -> a -> b
  infixr 0

Możemy też użyć wykrzyknika na parametrach konstruktorów danych:

  data StrictList t = StrictNil | !t :. !(StrictList t)
  
  data Employee = Employee
                    { name :: !Text
                    , age :: !Int
                    }

Rozszerzenie języka StrictData sprawia, że wszystkie parametry danych w danym module są ściśle ewaluowane.

Kolejne rozszerzenie, BangPattern, pozwala na używanie ! na argumentach funkcji. Z kolei rozszerzenie Strict zamienia wszystkie argumenty funkcji na ściśle ewaluowane.

W ekstremalnym przypadku możemy użyć ($!!) i typeklasy NFData do wymuszenia ewaluacji do postaci normalnej

  class NFData a where
    rnf :: a -> ()
  
  ($!!) :: (NFData a) => (a -> b) -> a -> b

jeśli tylko istnieje instancja tej typeklasy.

Kosztem ścisłej ewaluacji jest to, że Haskell zaczyna zachowywać się podobnie jak inne ścisłe języki i może wykonywać niepotrzebną pracę. Tym samym przełączanie się w ten tryb musi być wykonane z wielką uwagą i tylko gdy mamy do czynienia z mierzalnym wzrostem wydajności. Jeśli masz wątpliwości to lepiej zostać przy domyślnej leniwej ewaluacji.

Kolejne kroki

Haskell jest językiem często szybszym, bezpieczniejszym i prostszym niż Scala, który używany jest również w biznesie. Rozważ kurs programowania funkcyjnego od data61, a ewentualne pytania możesz zawsze zadać w pokoju #qfpl na freenode.net.

O to parę dodatkowych materiałów, które mogą być pomocne w nauce:

Jeśli podoba Ci się Haskell i doceniasz wartość jaką może przynieść twojej firmie, to powiedz to swoim przełożonym! W ten sposób ci nieliczni managerowie, którzy zdecydują się na ten krok mogą przyciągnąć utalentowanych programistów funkcyjnych z miejsc, które nie były dość odważne, a wszyscy będą szczęśliwi.

Up next

Licencje