-
Notifications
You must be signed in to change notification settings - Fork 18
Expand file tree
/
Copy pathLessons-Lesson02.html
More file actions
38 lines (38 loc) · 13.9 KB
/
Lessons-Lesson02.html
File metadata and controls
38 lines (38 loc) · 13.9 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><meta name="viewport" content="width=device-width, initial-scale=1" /><title>Lessons.Lesson02</title><link href="linuwial.css" rel="stylesheet" type="text/css" title="Linuwial" /><link rel="stylesheet" type="text/css" href="quick-jump.css" /><link rel="stylesheet" type="text/css" href="https://fonts.googleapis.com/css?family=PT+Sans:400,400i,700" /><script src="haddock-bundle.min.js" async="async" type="text/javascript"></script><script type="text/x-mathjax-config">MathJax.Hub.Config({ tex2jax: { processClass: "mathjax", ignoreClass: ".*" } });</script><script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML" type="text/javascript"></script></head><body><div id="package-header"><span class="caption empty"> </span><ul class="links" id="page-menu"><li><a href="src/Lessons.Lesson02.html">Source</a></li><li><a href="index.html">Contents</a></li><li><a href="doc-index.html">Index</a></li></ul></div><div id="content"><div id="module-header"><table class="info"><tr><th>Safe Haskell</th><td>Safe-Inferred</td></tr></table><p class="caption">Lessons.Lesson02</p></div><div id="description"><p class="caption">Description</p><div class="doc"><p>Notes taken by Ugnė Pacevičiūtė </p><p>In this lesson we will discuss two main topics: recursion and
Algebraic Data Types (ADT).</p></div></div><div id="synopsis"><details id="syn"><summary>Synopsis</summary><ul class="details-toggle" data-details-id="syn"><li class="src short"><a href="#v:f">f</a> :: [Integer] -> Integer</li><li class="src short"><a href="#v:f-39-">f'</a> :: [Integer] -> Integer</li><li class="src short"><a href="#v:length-39-">length'</a> :: [a] -> Int</li><li class="src short"><a href="#v:length-39--39-">length''</a> :: [a] -> Int</li><li class="src short"><a href="#v:t1">t1</a> :: (Integer, Char)</li><li class="src short"><a href="#v:t2">t2</a> :: (Integer, Int, String)</li><li class="src short"><a href="#v:trd">trd</a> :: (a, b, c) -> c</li><li class="src short"><span class="keyword">data</span> <a href="#t:FireExtinguisher">FireExtinguisher</a> = <a href="#v:FireExtinguisher">FireExtinguisher</a> Integer <a href="Lessons-Lesson02.html#t:FEType" title="Lessons.Lesson02">FEType</a></li><li class="src short"><span class="keyword">data</span> <a href="#t:FEType">FEType</a><ul class="subs"><li>= <a href="#v:A">A</a></li><li>| <a href="#v:B">B</a></li><li>| <a href="#v:C">C</a></li></ul></li><li class="src short"><a href="#v:capacity">capacity</a> :: <a href="Lessons-Lesson02.html#t:FireExtinguisher" title="Lessons.Lesson02">FireExtinguisher</a> -> Integer</li><li class="src short"><a href="#v:refill">refill</a> :: <a href="Lessons-Lesson02.html#t:FireExtinguisher" title="Lessons.Lesson02">FireExtinguisher</a> -> <a href="Lessons-Lesson02.html#t:FireExtinguisher" title="Lessons.Lesson02">FireExtinguisher</a></li></ul></details></div><div id="interface"><h1>Documentation</h1><div class="top"><p class="src"><a id="v:f" class="def">f</a> :: [Integer] -> Integer <a href="src/Lessons.Lesson02.html#f" class="link">Source</a> <a href="#v:f" class="selflink">#</a></p><div class="doc"><p>This is the first example of a recursive function.
Since Haskell is ummutable, we cannot have loops like one would
have in C, Java or C#. Recursion is the only awailable tool.</p><p>Also it uses a technique called pattern matching: a function might
have a few body lines which are tested top-down. The first matching
the actual arguments is applied.
Underscore matches any element but ignores it. <code>:</code> deconstructs a list
into a head (single first element) and a tail (a list of elements w/o the head).</p><p>The function return the head of a list, or 0 if the list is empty.</p><pre class="screen"><code class="prompt">>>> </code><strong class="userinput"><code>f []
</code></strong>0
</pre><pre class="screen"><code class="prompt">>>> </code><strong class="userinput"><code>f [1,2,3]
</code></strong>1
</pre></div></div><div class="top"><p class="src"><a id="v:f-39-" class="def">f'</a> :: [Integer] -> Integer <a href="src/Lessons.Lesson02.html#f%27" class="link">Source</a> <a href="#v:f-39-" class="selflink">#</a></p><div class="doc"><p>This pattern matching is dangerous, if only one-element list is
provided to the function it throws an exception.</p><pre class="screen"><code class="prompt">>>> </code><strong class="userinput"><code>f' []
</code></strong>0
</pre><pre class="screen"><code class="prompt">>>> </code><strong class="userinput"><code>f' [1]
</code></strong>/workspaces/fp-2025/src/Lessons/Lesson02.hs:(40,1)-(41,9): Non-exhaustive patterns in function f'
</pre><pre class="screen"><code class="prompt">>>> </code><strong class="userinput"><code>f' [1,2]
</code></strong>1
</pre></div></div><div class="top"><p class="src"><a id="v:length-39-" class="def">length'</a> :: [a] -> Int <a href="src/Lessons.Lesson02.html#length%27" class="link">Source</a> <a href="#v:length-39-" class="selflink">#</a></p><div class="doc"><p>Let's implement our first recursive function! It calculates a length of
a list (with elements of any type <code>a</code>). </p><p>This function is mathematically correct but it consumes stack space to keep
intermediate "+" arguments. So this function will fail on "large" lists.</p></div></div><div class="top"><p class="src"><a id="v:length-39--39-" class="def">length''</a> :: [a] -> Int <a href="src/Lessons.Lesson02.html#length%27%27" class="link">Source</a> <a href="#v:length-39--39-" class="selflink">#</a></p><div class="doc"><p>To eliminate this drawback using a <a href="https://en.wikipedia.org/wiki/Tail_call">Tail call optimization</a>.
We need the recursive call to be a final action of the function.</p><p>To achieve this we will have to introduce an additional parameter acc - accumulator where
we will collect intermediate results (and not on a top of the stack).</p></div></div><div class="top"><p class="src"><a id="v:t1" class="def">t1</a> :: (Integer, Char) <a href="src/Lessons.Lesson02.html#t1" class="link">Source</a> <a href="#v:t1" class="selflink">#</a></p><div class="doc"><p>Now let's switch to "data structures".</p><p>A tuple is fixed-size structure which can contain different type elements </p></div></div><div class="top"><p class="src"><a id="v:t2" class="def">t2</a> :: (Integer, Int, String) <a href="src/Lessons.Lesson02.html#t2" class="link">Source</a> <a href="#v:t2" class="selflink">#</a></p><div class="doc"><p>Three element's tuple</p></div></div><div class="top"><p class="src"><a id="v:trd" class="def">trd</a> :: (a, b, c) -> c <a href="src/Lessons.Lesson02.html#trd" class="link">Source</a> <a href="#v:trd" class="selflink">#</a></p><div class="doc"><p>Tuples can be pattern-matched.</p><p>This function is also an example of "parametric polymorphism": we have no
concrete types, only type variables which are not know at the time of function
declaretion but will be know at compilation time</p><pre class="screen"><code class="prompt">>>> </code><strong class="userinput"><code>trd (1, 10.09, "labas")
</code></strong>"labas"
</pre></div></div><div class="top"><p class="src"><span class="keyword">data</span> <a id="t:FireExtinguisher" class="def">FireExtinguisher</a> <a href="src/Lessons.Lesson02.html#FireExtinguisher" class="link">Source</a> <a href="#t:FireExtinguisher" class="selflink">#</a></p><div class="doc"><p>ADT - Algerbraic data type - is way to define custom "data structures".
Left hand side is a type (name). Right hand side is a list of constructors.
Please ignore the "deriving Show" part of the declarations, it just says
the GHC compiler to generate a default String representation of the ADT.
We will be back to this question soon.</p><p>One way to define an ADT is just a "named tuple". It acts like a tuple but has a name:
<code><a href="Lessons-Lesson02.html#t:FireExtinguisher" title="Lessons.Lesson02">FireExtinguisher</a></code> is a constructor with two arguments <code>Integer</code>
AND <code><a href="Lessons-Lesson02.html#t:FEType" title="Lessons.Lesson02">FEType</a></code>. To create a <code><a href="Lessons-Lesson02.html#t:FireExtinguisher" title="Lessons.Lesson02">FireExtinguisher</a></code> you have to pass both of them.</p><p>Constructors act like ordinary functions:</p><pre class="screen"><code class="prompt">>>> </code><strong class="userinput"><code>:t FireExtinguisher 10
</code></strong>FireExtinguisher 10 :: FEType -> FireExtinguisher
</pre></div><div class="subs constructors"><p class="caption">Constructors</p><table><tr><td class="src"><a id="v:FireExtinguisher" class="def">FireExtinguisher</a> Integer <a href="Lessons-Lesson02.html#t:FEType" title="Lessons.Lesson02">FEType</a></td><td class="doc empty"> </td></tr></table></div><div class="subs instances"><h4 class="instances details-toggle-control details-toggle" data-details-id="i:FireExtinguisher">Instances</h4><details id="i:FireExtinguisher" open="open"><summary class="hide-when-js-enabled">Instances details</summary><table><tr><td class="src clearfix"><span class="inst-left"><span class="instance details-toggle-control details-toggle" data-details-id="i:id:FireExtinguisher:Show:1"></span> Show <a href="Lessons-Lesson02.html#t:FireExtinguisher" title="Lessons.Lesson02">FireExtinguisher</a></span> <a href="src/Lessons.Lesson02.html#line-101" class="link">Source</a> <a href="#t:FireExtinguisher" class="selflink">#</a></td><td class="doc empty"> </td></tr><tr><td colspan="2"><details id="i:id:FireExtinguisher:Show:1"><summary class="hide-when-js-enabled">Instance details</summary><p>Defined in <a href="Lessons-Lesson02.html">Lessons.Lesson02</a></p> <div class="subs methods"><p class="caption">Methods</p><p class="src"><a href="#v:showsPrec">showsPrec</a> :: Int -> <a href="Lessons-Lesson02.html#t:FireExtinguisher" title="Lessons.Lesson02">FireExtinguisher</a> -> ShowS</p><p class="src"><a href="#v:show">show</a> :: <a href="Lessons-Lesson02.html#t:FireExtinguisher" title="Lessons.Lesson02">FireExtinguisher</a> -> String</p><p class="src"><a href="#v:showList">showList</a> :: [<a href="Lessons-Lesson02.html#t:FireExtinguisher" title="Lessons.Lesson02">FireExtinguisher</a>] -> ShowS</p></div></details></td></tr></table></details></div></div><div class="top"><p class="src"><span class="keyword">data</span> <a id="t:FEType" class="def">FEType</a> <a href="src/Lessons.Lesson02.html#FEType" class="link">Source</a> <a href="#t:FEType" class="selflink">#</a></p><div class="doc"><p>You might have a few constructors for a ADT. <code><a href="Lessons-Lesson02.html#t:FEType" title="Lessons.Lesson02">FEType</a></code> can be create by calling the
<code><a href="Lessons-Lesson02.html#v:A" title="Lessons.Lesson02">A</a></code> constructor OR <code><a href="Lessons-Lesson02.html#v:B" title="Lessons.Lesson02">B</a></code> constructor OR <code><a href="Lessons-Lesson02.html#v:C" title="Lessons.Lesson02">C</a></code> constructor.</p><pre class="screen"><code class="prompt">>>> </code><strong class="userinput"><code>A
</code></strong>A
</pre></div><div class="subs constructors"><p class="caption">Constructors</p><table><tr><td class="src"><a id="v:A" class="def">A</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a id="v:B" class="def">B</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a id="v:C" class="def">C</a></td><td class="doc empty"> </td></tr></table></div><div class="subs instances"><h4 class="instances details-toggle-control details-toggle" data-details-id="i:FEType">Instances</h4><details id="i:FEType" open="open"><summary class="hide-when-js-enabled">Instances details</summary><table><tr><td class="src clearfix"><span class="inst-left"><span class="instance details-toggle-control details-toggle" data-details-id="i:id:FEType:Show:1"></span> Show <a href="Lessons-Lesson02.html#t:FEType" title="Lessons.Lesson02">FEType</a></span> <a href="src/Lessons.Lesson02.html#line-108" class="link">Source</a> <a href="#t:FEType" class="selflink">#</a></td><td class="doc empty"> </td></tr><tr><td colspan="2"><details id="i:id:FEType:Show:1"><summary class="hide-when-js-enabled">Instance details</summary><p>Defined in <a href="Lessons-Lesson02.html">Lessons.Lesson02</a></p> <div class="subs methods"><p class="caption">Methods</p><p class="src"><a href="#v:showsPrec">showsPrec</a> :: Int -> <a href="Lessons-Lesson02.html#t:FEType" title="Lessons.Lesson02">FEType</a> -> ShowS</p><p class="src"><a href="#v:show">show</a> :: <a href="Lessons-Lesson02.html#t:FEType" title="Lessons.Lesson02">FEType</a> -> String</p><p class="src"><a href="#v:showList">showList</a> :: [<a href="Lessons-Lesson02.html#t:FEType" title="Lessons.Lesson02">FEType</a>] -> ShowS</p></div></details></td></tr></table></details></div></div><div class="top"><p class="src"><a id="v:capacity" class="def">capacity</a> :: <a href="Lessons-Lesson02.html#t:FireExtinguisher" title="Lessons.Lesson02">FireExtinguisher</a> -> Integer <a href="src/Lessons.Lesson02.html#capacity" class="link">Source</a> <a href="#v:capacity" class="selflink">#</a></p><div class="doc"><p>ADTs can be pattern matched.</p></div></div><div class="top"><p class="src"><a id="v:refill" class="def">refill</a> :: <a href="Lessons-Lesson02.html#t:FireExtinguisher" title="Lessons.Lesson02">FireExtinguisher</a> -> <a href="Lessons-Lesson02.html#t:FireExtinguisher" title="Lessons.Lesson02">FireExtinguisher</a> <a href="src/Lessons.Lesson02.html#refill" class="link">Source</a> <a href="#v:refill" class="selflink">#</a></p><div class="doc"><p>Usually you create new ADTs based on already existing ones.</p></div></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.29.2</p></div></body></html>