Document the Semigroup for Map
[packages/containers.git] / docs / sequence.rst
1 Sequences
2 =========
3
4 .. highlight:: haskell
5
6 Sequences allow you to store a finite number of sequential elements, providing
7 fast access to both ends of the sequence as well as efficient concatenation. The
8 ``containers`` package provides the :haddock:`/Data.Sequence` module which
9 defines the ``Seq`` data type.
10
11
12 Short Example
13 -------------
14
15 The following GHCi session shows some of the basic sequence funcitonality::
16
17     -- Import the Seq type and operators for combining sequences unqualified.
18     -- Import the rest of the Sequence module qualified.
19     import Data.Sequence (Seq(..), (<|), (|>), (><))
20     import qualified Data.Sequence as Seq
21
22     let nums = Seq.fromList [1, 2, 3]
23
24
25     -- Put numbers on the front and back.
26     0 <| nums
27     > fromList [0,1,2,3]
28
29     nums |> 4
30     > fromList [1,2,3,4]
31
32
33     -- Reverse a sequence
34     Seq.reverse (Seq.fromList [0, 1, 2])
35     > fromList [2,1,0]
36
37
38     -- Put two sequences together.
39     (Seq.fromList [-2, -1]) >< nums
40     > fromList [-2,-1,0,1,2]
41
42
43     -- Check if a sequence is empty and check the length.
44     Seq.null nums
45     > False
46
47     Seq.length nums
48     > 3
49
50
51     -- Lookup an element at a certain index (since version 0.4.8).
52     Seq.lookup 2 nums
53     > Just 3
54
55     -- Or the unsafe version, you MUST check length beforehand.
56     Seq.index 2 nums
57     > 3
58
59
60     -- Map a function over a sequence (can use fmap or the infix function <$>).
61     fmap show nums
62     > fromList ["0","1","2"]
63
64     show <$> nums
65     > fromList ["0","1","2"]
66
67
68     -- Fold a sequence into a summary value.
69     foldr (+) 0 (Seq.fromList [0, 1, 2])
70     > 3
71
72 .. TIP:: You can use the `OverloadedLists
73          <http://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#overloaded-lists>`_
74          extension so you don't need to write ``fromList [1, 2, 3]`` everywhere.
75          Instead you can just write ``[1, 2, 3]`` and if the function is
76          expecting a sequence it will be converted automatically! The code here
77          will continue to use ``fromList`` for clarity.
78
79
80 Importing Sequence
81 ------------------
82
83 When using ``Sequence`` in a Haskell source file you should always use a
84 ``qualified`` import becasue it exports names that clash with the standard
85 Prelude (you can import the type constructor and some operators on their own
86 though!).
87
88 ::
89
90     import Data.Sequence (Seq, (<|), (|>), (><))
91     import qualified Data.Sequence as Seq
92
93
94 Common API Functions
95 --------------------
96
97 .. NOTE::
98    ``fromList [some,sequence,elements]`` is how a ``Seq`` is printed.
99
100 Construction and Conversion
101 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
102
103 Create an empty sequence
104 """"""""""""""""""""""""
105
106 ::
107
108     Seq.empty :: Seq a
109     Seq.empty = ...
110
111 :haddock_short:`/Data.Sequence#empty` creates a sequence with zero elements.
112
113 ::
114
115     Seq.empty
116     > fromList []
117
118
119 Create a sequence with one element (singleton)
120 """"""""""""""""""""""""""""""""""""""""""""""
121
122 ::
123
124     Seq.singleton :: a -> Seq a
125     Seq.singleton x = ...
126
127 :haddock_short:`/Data.Sequence#singleton` creates a sequence with the single
128 element ``x`` in it.
129
130 ::
131
132     Seq.singleton "containers"
133     > fromList ["containers"]
134
135     Seq.singleton 1
136     > fromList [1]
137
138 Create a sequence with the same element repeated
139 """"""""""""""""""""""""""""""""""""""""""""""""
140
141 ::
142
143     Seq.replicate :: Int -> a -> Seq a
144     Seq.replicate n x = ...
145
146 :haddock_short:`/Data.Sequence#replicate` creates a sequence with same element
147 ``x`` repeated ``n`` times.
148
149 ::
150
151     Seq.replicate 0 "hi"
152     > fromList []
153
154     Seq.replicate 3 "hi"
155     > fromList ["hi","hi","hi"]
156
157 Create a sequence from a list
158 """""""""""""""""""""""""""""
159
160 ::
161
162     Seq.fromList :: [a] -> Seq a
163     Seq.FromList xs = ...
164
165 :haddock_short:`/Data.Sequence#fromList` creates a sequence containing the
166 elements of the list ``xs``. Sequences allow duplicate so all elements will be
167 included in the order given.
168
169 ::
170
171     Seq.fromList ["base", "containers", "QuickCheck"]
172     > fromList ["base","containers","QuickCheck"]
173
174     Seq.fromList [0, 1, 1, 2, 3, 1]
175     > fromList [0,1,1,2,3,1]
176
177 Adding to an existing sequence
178 """"""""""""""""""""""""""""""
179
180 ::
181
182     (<|) :: a -> Seq a -> Seq a
183     x <| xs = ...
184
185     (|>) :: Seq a -> a -> Seq a
186     xs |> x = ...
187
188     (><) :: Seq a -> Seq a -> Seq a
189     l >< r = ...
190
191 - ``x <| xs`` places the element ``x`` at the beginning of the sequence ``xs``.
192
193 - ``xs |> x`` places the element ``x`` at the end of the sequence ``xs``.
194
195 - ``l >< r`` combines the two sequences ``l`` and ``r`` together.
196
197
198 Create a list from a sequence
199 """""""""""""""""""""""""""""
200
201 ::
202
203     import qualified Data.Foldable as Foldable
204     Foldable.toList :: Seq a -> [a]
205
206
207 There is no ``toList`` function in the Sequence module since it can be
208 `easily implemented <https://wiki.haskell.org/Foldable_and_Traversable>`_ with a
209 fold using ``Seq``'s `Foldable
210 <https://wiki.haskell.org/Typeclassopedia#Foldable>`_ instance.
211
212 ::
213
214     import qualified Data.Foldable as Foldable
215     Foldable.toList (Seq.fromList ["base", "containers", "QuickCheck"])
216     > ["base","containers","QuickCheck"]
217
218
219 Pattern Matching
220 ^^^^^^^^^^^^^^^^
221
222 *Since 0.5.10*
223
224 Just like you can pattern match (aka. destructure) a list ``[a]``, you can do
225 the same with sequences. Let's first look at how we do this with lists::
226
227     case [1, 2, 3] of
228       [] -> "empty list"
229       (x:xs) -> "first:" ++ show x ++ " rest:" ++ show xs
230     > "first:1 rest:[2,3]"
231
232
233 Let's do the same thing with sequences!
234
235 ::
236
237     -- Imports the patterns to match on.
238     import Data.Sequence (Seq (Empty, (:<|), (:|>)))
239
240     case Seq.fromList [1, 2, 3] of
241       Empty -> "empty sequence"
242       x :<| xs -> "first:" ++ x ++ " rest:" ++ show xs
243     > "first:1 rest:fromList [2,3]"
244
245 .. NOTE:: You can't copy/paste this into GHCi because it's multiple lines.
246
247 You can also take an element off the end::
248
249     -- Imports the patterns to match on.
250     import Data.Sequence (Seq (Empty, (:<|), (:|>)))
251
252     case Seq.fromList [1, 2, 3] of
253       Empty -> "empty sequence"
254       xs :|> x -> "last element:" ++ show x
255     > "last element:3"
256
257 Querying
258 ^^^^^^^^
259
260 Check if a sequence is empty
261 """"""""""""""""""""""""""""
262
263 ::
264
265     Seq.null :: Seq a -> Bool
266     Seq.null xs = ...
267
268 :haddock_short:`/Data.Sequence#null` returns ``True`` if the sequence ``xs`` is
269 empty, and ``False`` otherwise.
270
271 ::
272
273     Seq.null Seq.empty
274     > True
275
276     Seq.null (Seq.fromList [1, 2, 3])
277     > False
278
279 The length/size of a sequence
280 """""""""""""""""""""""""""""
281
282 ::
283
284     Seq.length :: Seq a -> Int
285     Seq.length xs = ...
286
287 :haddock_short:`/Data.Sequence#length` returns the length of the sequence ``xs``.
288
289 ::
290
291     Seq.length Seq.empty
292     > 0
293
294     Seq.length (Seq.fromList [1, 2, 3])
295     > 3
296
297 The element at a given index
298 """"""""""""""""""""""""""""
299
300 ::
301
302     Seq.lookup :: Int -> Seq a -> Maybe a
303     Seq.lookup n xs = ...
304
305     Seq.!? :: Seq a -> Int -> Maybe a
306     xs !? n = ...
307
308 :haddock_short:`/Data.Sequence#lookup` returns the element at the position ``n``,
309 or ``Nothing`` if the index is out of bounds. :haddock_short:`/Data.Sequence#!?`
310 is simply a flipped version of ``lookup``.
311
312 .. NOTE::
313    You may need to import ``!?`` qualified if you're using a ``Map``,
314    ``IntMap``, or ``Vector`` in the same file because they all export the
315    same operator.
316
317 ::
318
319     Seq.index :: Seq a -> Int -> a
320     Seq.index xs n = ...
321
322 :haddock_short:`/Data.Sequence#index` returns the element at the given
323 position. It throws a runtime error if the index is out of bounds.
324
325 .. TIP::
326    Use ``lookup``/``!?`` whenever you can and explicitly deal with the
327    ``Nothing`` case.
328
329 ::
330
331     (Seq.fromList ["base", "containers"]) Seq.!? 0
332     > Just "base"
333
334     Seq.index 0 (Seq.fromList ["base", "containers"])
335     > "base"
336
337     (Seq.fromList ["base", "containers"]) Seq.!? 2
338     > Nothing
339
340     Seq.index (Seq.fromList ["base", "containers"]) 2
341     > "*** Exception: index out of bounds
342
343 When working with functions that return a ``Maybe v``, use a `case expression
344 <https://en.wikibooks.org/wiki/Haskell/Control_structures#case_expressions>`_ to
345 deal with the ``Just`` or ``Nothing`` value::
346
347    do
348      let firstDependency = Seq.fromList ["base", "containers"] !? 0
349      case firstDependency of
350        Nothing -> print "Whoops! No dependencies!"
351        Just dep -> print "The first dependency is " ++ dep
352
353
354 Modification
355 ^^^^^^^^^^^^
356
357 Inserting an element
358 """"""""""""""""""""
359
360 ::
361
362     Seq.insertAt :: Int -> a -> Seq a -> Seq a
363     Seq.insertAt i x xs = ...
364
365 :haddock_short:`/Data.Sequence#insertAt` inserts ``x`` into ``xs`` at the index
366 ``i``, shifting the rest of the sequence over. If ``i`` is out of range then
367 ``x`` will be inserted at the beginning or the end of the sequence as
368 appropriate.
369
370 ::
371
372     Seq.insertAt 0 "idris" (Seq.fromList ["haskell", "rust"])
373     > fromList ["idris","haskell","rust"]
374
375     Seq.insertAt (-10) "idris" (Seq.fromList ["haskell", "rust"])
376     > fromList ["idris","haskell","rust"]
377
378     Seq.insertAt 10 "idris" (Seq.fromList ["haskell", "rust"])
379     > fromList ["haskell","rust","idris"]
380
381 See also `Adding to an existing sequence`_.
382
383 Delete an element
384 """""""""""""""""
385
386 ::
387
388     Seq.deleteAt :: Int -> Seq a -> Seq a
389     Seq.deleteAt i xs = ...
390
391 :haddock_short:`/Data.Sequence#deleteAt` removes the element of the sequence at
392 index ``i``. If the index is out of bounds then the original sequence is
393 returned.
394
395 ::
396
397     Seq.deleteAt 0 (Seq.fromList [0, 1, 2])
398     > fromList [1,2]
399
400     Seq.deleteAt 10 (Seq.fromList [0, 1, 2])
401     > fromList [0,1,2]
402
403 Replace an element
404 """"""""""""""""""
405
406 ::
407
408     Seq.update :: Int -> a -> Seq a -> Seq a
409     Seq.update i x xs = ...
410
411 :haddock_short:`/Data.Sequence#update` replaces the element at position ``i`` in
412 the sequence with ``x``. If the index is out of bounds then the original
413 sequence is returned.
414
415 ::
416
417     Seq.update 0 "hello" (Seq.fromList ["hi", "world", "!"])
418     > fromList ["hello","world","!"]
419
420     Seq.update 3 "OUTOFBOUNDS" (Seq.fromList ["hi", "world", "!"])
421     > fromList ["hi","world","!"]
422
423 Adjust/modify an element
424 """"""""""""""""""""""""
425
426 *Since version 0.5.8*
427
428 ::
429
430     adjust' :: forall a. (a -> a) -> Int -> Seq a -> Seq a
431     adjust' f i xs = ...
432
433 :haddock_short:`/Data.Sequence#adjust'` updates the element at position ``i`` in
434 the sequence by applying the function ``f`` to the existing element. If the
435 index is out of bounds then the original sequence is returned.
436
437 ::
438
439     Seq.adjust' (*10) 0 (Seq.fromList [1, 2, 3])
440     > fromList [10,2,3]
441
442     Seq.adjust' (*10) 3 (Seq.fromList [1, 2, 3])
443     > fromList [1,2,3]
444
445 .. NOTE::
446    If you're using an older version of containers which only has ``adjust``, be
447    careful because it can lead to poor performance and space leaks (see
448    :haddock_short:`/Data.Sequence#adjust` docs).
449
450 Modifying all elements
451 """"""""""""""""""""""
452
453 ::
454
455     fmap :: (a -> b) -> Seq a -> Seq b
456     fmap f xs = ...
457
458     Seq.mapWithIndex :: (Int -> a -> b) -> Seq a -> Seq b
459     Seq.mapWithIndex f xs = ...
460
461 :haddock_short:`/Data.Sequence#fmap` transform each element of the sequence with
462 the function ``f``. ``fmap`` is provided by the `Functor
463 <https://wiki.haskell.org/Typeclassopedia#Functor>`_ instance for sequences and
464 can also be written infix using the ``<$>`` operator.
465
466 :haddock_short:`/Data.Sequence#mapWithIndex` allows you to do a similar
467 transformation but gives you the index that each element is at.
468
469 ::
470
471     fmap (*10) (Seq.fromList [1, 2, 3])
472     -- = fromList [1*10, 2*10, 3*10]
473     > fromList [10,20,30]
474
475     (*10) <$> Seq.fromList [1, 2, 3]
476     -- = fromList [1*10, 2*10, 3*10]
477     > fromList [10,20,30]
478
479     let myMapFunc index val = index * val
480
481     Seq.mapWithIndex myMapFunc (Seq.fromList [1, 2, 3])
482     -- = fromList [0*1, 1*2, 2*3]
483     > fromList [0,2,6]
484
485
486 Sorting
487 ^^^^^^^
488
489 ::
490
491     Seq.sort :: Ord a => Seq a -> Seq a
492     Seq.sort xs = ...
493
494 :haddock_short:`/Data.Sequence#sort` the sequence ``xs`` using the ``Ord``
495 instance.
496
497 ::
498
499     Seq.sort (Seq.fromList ["x", "a", "c", "b"])
500     > fromList ["a","b","c","x"]
501
502
503 Subsequences
504 ^^^^^^^^^^^^
505
506 Take
507 """"
508
509 ::
510
511     Seq.take :: Int -> Seq a -> Seq a
512     Seq.take n xs = ...
513
514 :haddock_short:`/Data.Sequence#take` returns the first ``n`` elements of the
515 sequence ``xs``. If the length of ``xs`` is less than ``n`` then all elements
516 are returned.
517
518 ::
519
520     Seq.take 0 (Seq.fromList [1, 2, 3])
521     > fromList []
522
523     Seq.take 2 (Seq.fromList [1, 2, 3])
524     > fromList [1,2]
525
526     Seq.take 5 (Seq.fromList [1, 2, 3])
527     > fromList [1,2,3]
528
529 Drop
530 """"
531
532 ::
533
534     Seq.drop :: Int -> Seq a -> Seq a
535     Seq.drop n xs = ...
536
537 :haddock_short:`/Data.Sequence#drop` the first ``n`` elements of the sequence
538 ``xs``. If the length of ``xs`` is less than ``n`` then an empty sequence is
539 returned.
540
541 ::
542
543     Seq.drop 0 (Seq.fromList [1, 2, 3])
544     > fromList [1,2,3]
545
546     Seq.drop 2 (Seq.fromList [1, 2, 3])
547     > fromList [3]
548
549     Seq.drop 5 (Seq.fromList [1, 2, 3])
550     > fromList []
551
552 Chunks
553 """"""
554
555 ::
556
557     Seq.chunksOf :: Int -> Seq a -> Seq (Seq a)
558     Seq.chunksOf k xs = ...
559
560 :haddock_short:`/Data.Sequence#chunksOf` splits the sequence ``xs`` into chunks
561 of size ``k``. If the length of the sequence is not evenly divisible by ``k``
562 then the last chunk will have less than ``k`` elements.
563
564 .. WARNING::
565    ``k`` can only be ``0`` when the sequence is empty, otherwise a runtime
566    error is thrown.
567
568 ::
569
570     -- A chunk size of 0 can ONLY be given for an empty sequence.
571     Seq.chunksOf 0 Seq.empty
572     > fromList []
573
574     Seq.chunksOf 1 (Seq.fromList [1, 2, 3])
575     > fromList [fromList [1],fromList [2],fromList [3]]
576
577     Seq.chunksOf 2 (Seq.fromList [1, 2, 3])
578     > fromList [fromList [1,2],fromList [3]]
579
580     Seq.chunksOf 5 (Seq.fromList [1, 2, 3])
581     > fromList [fromList [1,2,3]]
582
583
584 Folding
585 ^^^^^^^
586
587 ::
588
589     foldr :: (a -> b -> b) -> b -> Seq a -> b
590     foldr f init xs = ...
591
592     Seq.foldrWithIndex :: (Int -> a -> b -> b) -> b -> Seq a -> b
593     Seq.foldrWithIndex f init xs = ...
594
595 :haddock_short:`/Data.Sequence#foldr` collapses the sequence into a summary
596 value by repeatedly applying ``f``. ``foldr`` is provided by the `Foldable
597 <https://wiki.haskell.org/Typeclassopedia#Foldable>`_ instance for
598 sequences. :haddock_short:`/Data.Sequence#foldWithIndex` gives you access to the
599 position in the sequence when transforming each element.
600
601 ::
602
603     foldr (+) 0 (Seq.fromList [1, 2, 3])
604     -- = (1 + (2 + (3 + 0)))
605     > 6
606
607     let myFoldFunction index val accum = (index * val) + accum
608
609     Seq.foldrWithIndex myFoldFunction 0 (Seq.fromList [1, 2, 3])
610     -- = ((0*1) + ((1*2) + ((2*3) + 0)))
611     > 8
612
613
614 Serialization
615 -------------
616
617 The best way to serialize and deserialize sequences is to use one of the many
618 libraries which already support serializing sequences. :haddock:`binary`,
619 :haddock:`cereal`, and :haddock:`store` are some common libraries that people
620 use.
621
622
623 Performance
624 -----------
625
626 The API docs are annotated with the Big-*O* complexities of each of the sequence
627 operations. For benchmarks see the `haskell-perf/sequences
628 <https://github.com/haskell-perf/sequences>`_ page.
629
630
631 Looking for more?
632 -----------------
633
634 Didn't find what you're looking for? This tutorial only covered the most common
635 sequence functions, for a full list of functions see the
636 :haddock:`/Data.Sequence` API documentation.