0
# Data Structures
1
2
Scalaz provides immutable functional data structures designed for composition, safety, and performance in functional programming contexts.
3
4
## Capabilities
5
6
### Either-like Types
7
8
#### Disjunction (\/)
9
10
Right-biased either-like type for representing computations that may fail or have two possible outcomes.
11
12
```scala { .api }
13
sealed abstract class \/[+A, +B] {
14
/** Map over the right side */
15
def map[C](f: B => C): A \/ C
16
17
/** FlatMap over the right side */
18
def flatMap[C](f: B => A \/ C): A \/ C
19
20
/** Check if this is a left value */
21
def isLeft: Boolean
22
23
/** Check if this is a right value */
24
def isRight: Boolean
25
26
/** Fold both sides */
27
def fold[C](fa: A => C, fb: B => C): C
28
29
/** Swap left and right */
30
def swap: B \/ A
31
32
/** Convert to Either */
33
def toEither: Either[A, B]
34
35
/** Convert to Option, discarding left */
36
def toOption: Option[B]
37
38
/** Get the right value or a default */
39
def getOrElse[BB >: B](x: => BB): BB
40
41
/** Recover from left with a function */
42
def recover[BB >: B](pf: PartialFunction[A, BB]): A \/ BB
43
44
/** Transform left side */
45
def leftMap[C](f: A => C): C \/ B
46
}
47
48
/** Left constructor */
49
case class -\/[+A](a: A) extends (A \/ Nothing)
50
51
/** Right constructor */
52
case class \/-[+B](b: B) extends (Nothing \/ B)
53
54
object \/ {
55
/** Create left value */
56
def left[A, B](a: A): A \/ B = -\/(a)
57
58
/** Create right value */
59
def right[A, B](b: B): A \/ B = \/-(b)
60
61
/** Try operation, catching exceptions as left */
62
def fromTryCatchThrowable[T, E <: Throwable](a: => T)(implicit nn: NotNothing[E], ex: ClassTag[E]): E \/ T
63
}
64
```
65
66
**Usage Examples:**
67
68
```scala
69
import scalaz._
70
import Scalaz._
71
72
// Creating disjunctions
73
val success: String \/ Int = \/-(42)
74
val failure: String \/ Int = -\/("error")
75
76
// Mapping and chaining
77
val result = for {
78
x <- \/-(10)
79
y <- \/-(20)
80
} yield x + y // \/-(30)
81
82
// Error handling
83
val safe = \/.fromTryCatchThrowable[Int, NumberFormatException]("42".toInt)
84
```
85
86
#### Validation
87
88
Like Disjunction but designed for error accumulation using Applicative.
89
90
```scala { .api }
91
sealed abstract class Validation[+E, +A] {
92
/** Map over success value */
93
def map[B](f: A => B): Validation[E, B]
94
95
/** Applicative apply for error accumulation */
96
def ap[EE >: E, B](f: => Validation[EE, A => B])(implicit E: Semigroup[EE]): Validation[EE, B]
97
98
/** Check if this is a failure */
99
def isFailure: Boolean
100
101
/** Check if this is a success */
102
def isSuccess: Boolean
103
104
/** Fold both cases */
105
def fold[B](failure: E => B, success: A => B): B
106
107
/** Convert to Disjunction */
108
def disjunction: E \/ A
109
110
/** Convert to Option */
111
def toOption: Option[A]
112
113
/** Get success value or default */
114
def getOrElse[AA >: A](x: => AA): AA
115
}
116
117
/** Failure case */
118
case class Failure[+E](e: E) extends Validation[E, Nothing]
119
120
/** Success case */
121
case class Success[+A](a: A) extends Validation[Nothing, A]
122
123
object Validation {
124
/** Create success */
125
def success[E, A](a: A): Validation[E, A] = Success(a)
126
127
/** Create failure */
128
def failure[E, A](e: E): Validation[E, A] = Failure(e)
129
130
/** Create success for non-empty list validation */
131
def successNel[E, A](a: A): ValidationNel[E, A] = Success(a)
132
133
/** Create failure for non-empty list validation */
134
def failureNel[E, A](e: E): ValidationNel[E, A] = Failure(NonEmptyList(e))
135
}
136
137
type ValidationNel[E, +A] = Validation[NonEmptyList[E], A]
138
```
139
140
**Usage Examples:**
141
142
```scala
143
import scalaz._
144
import Scalaz._
145
146
// Error accumulation
147
val user = (
148
validateName("John").toValidationNel |@|
149
validateAge(25).toValidationNel |@|
150
validateEmail("john@example.com").toValidationNel
151
) { User(_, _, _) }
152
153
// Multiple errors will be accumulated in NonEmptyList
154
```
155
156
### Collection Types
157
158
#### NonEmptyList
159
160
A list guaranteed to contain at least one element.
161
162
```scala { .api }
163
sealed abstract class NonEmptyList[+A] {
164
/** The first element */
165
def head: A
166
167
/** The rest of the elements */
168
def tail: List[A]
169
170
/** Total size */
171
def size: Int
172
173
/** Map over elements */
174
def map[B](f: A => B): NonEmptyList[B]
175
176
/** FlatMap over elements */
177
def flatMap[B](f: A => NonEmptyList[B]): NonEmptyList[B]
178
179
/** Append another NonEmptyList */
180
def append[AA >: A](other: NonEmptyList[AA]): NonEmptyList[AA]
181
182
/** Prepend an element */
183
def prepend[AA >: A](a: AA): NonEmptyList[AA]
184
185
/** Convert to regular List */
186
def toList: List[A]
187
188
/** Reverse the list */
189
def reverse: NonEmptyList[A]
190
191
/** Take first n elements */
192
def take(n: Int): List[A]
193
194
/** Drop first n elements */
195
def drop(n: Int): List[A]
196
197
/** Zip with another NonEmptyList */
198
def zip[B](other: NonEmptyList[B]): NonEmptyList[(A, B)]
199
200
/** Fold the list */
201
def foldLeft[B](z: B)(f: (B, A) => B): B
202
def foldRight[B](z: => B)(f: (A, => B) => B): B
203
}
204
205
object NonEmptyList {
206
/** Create from head and tail */
207
def apply[A](head: A, tail: A*): NonEmptyList[A]
208
209
/** Create from List (returns Option) */
210
def fromList[A](list: List[A]): Option[NonEmptyList[A]]
211
212
/** Create single element NonEmptyList */
213
def nel[A](head: A, tail: List[A] = Nil): NonEmptyList[A]
214
}
215
```
216
217
#### IList (Immutable List)
218
219
Stack-safe immutable list implementation.
220
221
```scala { .api }
222
sealed abstract class IList[+A] {
223
/** Check if empty */
224
def isEmpty: Boolean
225
226
/** Check if non-empty */
227
def nonEmpty: Boolean
228
229
/** Head element (unsafe) */
230
def head: A
231
232
/** Tail elements (unsafe) */
233
def tail: IList[A]
234
235
/** Safe head */
236
def headOption: Option[A]
237
238
/** Safe tail */
239
def tailOption: Option[IList[A]]
240
241
/** Prepend element */
242
def ::[AA >: A](a: AA): IList[AA]
243
244
/** Append element */
245
def :+[AA >: A](a: AA): IList[AA]
246
247
/** Concatenate with another IList */
248
def ++[AA >: A](other: IList[AA]): IList[AA]
249
250
/** Map over elements */
251
def map[B](f: A => B): IList[B]
252
253
/** FlatMap over elements */
254
def flatMap[B](f: A => IList[B]): IList[B]
255
256
/** Filter elements */
257
def filter(p: A => Boolean): IList[A]
258
259
/** Length of the list */
260
def length: Int
261
262
/** Reverse the list */
263
def reverse: IList[A]
264
265
/** Convert to standard List */
266
def toList: List[A]
267
268
/** Fold operations */
269
def foldLeft[B](z: B)(f: (B, A) => B): B
270
def foldRight[B](z: => B)(f: (A, => B) => B): B
271
}
272
273
object IList {
274
/** Empty IList */
275
def empty[A]: IList[A]
276
277
/** Single element IList */
278
def single[A](a: A): IList[A]
279
280
/** Create from varargs */
281
def apply[A](as: A*): IList[A]
282
283
/** Create from List */
284
def fromList[A](list: List[A]): IList[A]
285
}
286
```
287
288
#### DList (Difference List)
289
290
Efficient list-like structure supporting O(1) append operations.
291
292
```scala { .api }
293
case class DList[A](f: List[A] => List[A]) {
294
/** Append another DList */
295
def ++(other: DList[A]): DList[A]
296
297
/** Prepend a single element */
298
def +:(a: A): DList[A]
299
300
/** Append a single element */
301
def :+(a: A): DList[A]
302
303
/** Convert to List */
304
def toList: List[A]
305
306
/** Check if empty */
307
def isEmpty: Boolean
308
309
/** Map over elements */
310
def map[B](f: A => B): DList[B]
311
312
/** FlatMap over elements */
313
def flatMap[B](f: A => DList[B]): DList[B]
314
}
315
316
object DList {
317
/** Empty DList */
318
def empty[A]: DList[A]
319
320
/** Single element DList */
321
def single[A](a: A): DList[A]
322
323
/** Create from List */
324
def fromList[A](list: List[A]): DList[A]
325
}
326
```
327
328
### Tree Structures
329
330
#### Tree
331
332
Multiway tree where each node contains a value and a stream of subtrees.
333
334
```scala { .api }
335
case class Tree[A](rootLabel: A, subForest: Stream[Tree[A]]) {
336
/** Map over all values in the tree */
337
def map[B](f: A => B): Tree[B]
338
339
/** FlatMap over the tree */
340
def flatMap[B](f: A => Tree[B]): Tree[B]
341
342
/** Get all values in pre-order */
343
def flatten: Stream[A]
344
345
/** Get all values in level-order */
346
def levels: Stream[Stream[A]]
347
348
/** Tree size (number of nodes) */
349
def size: Int
350
351
/** Tree height */
352
def height: Int
353
354
/** Check if tree is a leaf */
355
def isLeaf: Boolean
356
357
/** Convert to TreeLoc (zipper) */
358
def loc: TreeLoc[A]
359
360
/** Pretty print the tree */
361
def drawTree(implicit sh: Show[A]): String
362
363
/** Pre-order traversal */
364
def pre: Stream[A]
365
366
/** Post-order traversal */
367
def post: Stream[A]
368
}
369
370
object Tree {
371
/** Create a leaf node */
372
def leaf[A](a: A): Tree[A] = Tree(a, Stream.empty)
373
374
/** Create node with children */
375
def node[A](root: A, children: Stream[Tree[A]]): Tree[A] = Tree(root, children)
376
377
/** Unfold a tree from a seed */
378
def unfoldTree[A, B](seed: A)(f: A => (B, Stream[A])): Tree[B]
379
}
380
```
381
382
#### TreeLoc (Tree Zipper)
383
384
Zipper for Tree providing navigation and editing capabilities.
385
386
```scala { .api }
387
case class TreeLoc[A](tree: Tree[A], lefts: Stream[Tree[A]], rights: Stream[Tree[A]], parents: Stream[(Stream[Tree[A]], A, Stream[Tree[A]])]) {
388
/** Get the current label */
389
def getLabel: A
390
391
/** Set the current label */
392
def setLabel(a: A): TreeLoc[A]
393
394
/** Modify the current label */
395
def modifyLabel(f: A => A): TreeLoc[A]
396
397
/** Get current tree */
398
def getTree: Tree[A]
399
400
/** Set current tree */
401
def setTree(t: Tree[A]): TreeLoc[A]
402
403
/** Move to parent */
404
def parent: Option[TreeLoc[A]]
405
406
/** Move to first child */
407
def firstChild: Option[TreeLoc[A]]
408
409
/** Move to last child */
410
def lastChild: Option[TreeLoc[A]]
411
412
/** Move to left sibling */
413
def left: Option[TreeLoc[A]]
414
415
/** Move to right sibling */
416
def right: Option[TreeLoc[A]]
417
418
/** Move to root */
419
def root: TreeLoc[A]
420
421
/** Check if at root */
422
def isRoot: Boolean
423
424
/** Check if is first child */
425
def isFirst: Boolean
426
427
/** Check if is last child */
428
def isLast: Boolean
429
430
/** Check if is leaf */
431
def isLeaf: Boolean
432
433
/** Insert child at beginning */
434
def insertDownFirst(t: Tree[A]): TreeLoc[A]
435
436
/** Insert child at end */
437
def insertDownLast(t: Tree[A]): TreeLoc[A]
438
439
/** Insert left sibling */
440
def insertLeft(t: Tree[A]): TreeLoc[A]
441
442
/** Insert right sibling */
443
def insertRight(t: Tree[A]): TreeLoc[A]
444
445
/** Delete current node */
446
def delete: Option[TreeLoc[A]]
447
}
448
```
449
450
### Specialized Collections
451
452
#### Zipper
453
454
Functional cursor over a List providing O(1) navigation and editing.
455
456
```scala { .api }
457
case class Zipper[A](lefts: Stream[A], focus: A, rights: Stream[A]) {
458
/** Move focus left */
459
def left: Option[Zipper[A]]
460
461
/** Move focus right */
462
def right: Option[Zipper[A]]
463
464
/** Move to leftmost position */
465
def start: Zipper[A]
466
467
/** Move to rightmost position */
468
def end: Zipper[A]
469
470
/** Modify the focus */
471
def modify(f: A => A): Zipper[A]
472
473
/** Replace the focus */
474
def update(a: A): Zipper[A]
475
476
/** Insert element to the left */
477
def insertLeft(a: A): Zipper[A]
478
479
/** Insert element to the right */
480
def insertRight(a: A): Zipper[A]
481
482
/** Delete the focus */
483
def delete: Option[Zipper[A]]
484
485
/** Convert back to List */
486
def toList: List[A]
487
488
/** Convert to Stream */
489
def toStream: Stream[A]
490
491
/** Length of the zipper */
492
def length: Int
493
494
/** Check if at start */
495
def atStart: Boolean
496
497
/** Check if at end */
498
def atEnd: Boolean
499
}
500
501
object Zipper {
502
/** Create zipper from List */
503
def fromList[A](list: List[A]): Option[Zipper[A]]
504
505
/** Create zipper from Stream */
506
def fromStream[A](stream: Stream[A]): Option[Zipper[A]]
507
}
508
```
509
510
#### Heap
511
512
Priority queue implemented with bootstrapped skew binomial heaps.
513
514
```scala { .api }
515
sealed abstract class Heap[A] {
516
/** Check if heap is empty */
517
def isEmpty: Boolean
518
519
/** Size of the heap */
520
def size: Int
521
522
/** Insert element */
523
def insert(a: A)(implicit o: Order[A]): Heap[A]
524
525
/** Get minimum element */
526
def minimum: Option[A]
527
528
/** Remove minimum element */
529
def deleteMin(implicit o: Order[A]): Option[Heap[A]]
530
531
/** Extract minimum (get and remove) */
532
def uncons(implicit o: Order[A]): Option[(A, Heap[A])]
533
534
/** Union with another heap */
535
def union(other: Heap[A])(implicit o: Order[A]): Heap[A]
536
537
/** Convert to List (sorted) */
538
def toList(implicit o: Order[A]): List[A]
539
540
/** Convert to Stream (sorted) */
541
def toStream(implicit o: Order[A]): Stream[A]
542
}
543
544
object Heap {
545
/** Empty heap */
546
def empty[A]: Heap[A]
547
548
/** Single element heap */
549
def single[A](a: A): Heap[A]
550
551
/** Create heap from List */
552
def fromList[A](list: List[A])(implicit o: Order[A]): Heap[A]
553
}
554
```
555
556
### Maybe Type
557
558
#### Maybe
559
560
Scalaz's alternative to Option with better performance characteristics.
561
562
```scala { .api }
563
sealed abstract class Maybe[+A] {
564
/** Check if this contains a value */
565
def isDefined: Boolean
566
567
/** Check if this is empty */
568
def isEmpty: Boolean
569
570
/** Map over the contained value */
571
def map[B](f: A => B): Maybe[B]
572
573
/** FlatMap over the contained value */
574
def flatMap[B](f: A => Maybe[B]): Maybe[B]
575
576
/** Get value or default */
577
def getOrElse[AA >: A](a: => AA): AA
578
579
/** Convert to Option */
580
def toOption: Option[A]
581
582
/** Fold with functions for both cases */
583
def fold[B](ifEmpty: => B)(f: A => B): B
584
585
/** Filter with predicate */
586
def filter(p: A => Boolean): Maybe[A]
587
588
/** Check if value satisfies predicate */
589
def exists(p: A => Boolean): Boolean
590
591
/** Check if value satisfies predicate or is empty */
592
def forall(p: A => Boolean): Boolean
593
594
/** Apply side effect if value exists */
595
def foreach(f: A => Unit): Unit
596
597
/** Convert to List */
598
def toList: List[A]
599
}
600
601
/** Contains a value */
602
case class Just[+A](a: A) extends Maybe[A]
603
604
/** Contains no value */
605
case object Empty extends Maybe[Nothing]
606
607
object Maybe {
608
/** Create Maybe from value */
609
def just[A](a: A): Maybe[A] = Just(a)
610
611
/** Empty Maybe */
612
def empty[A]: Maybe[A] = Empty
613
614
/** Create from Option */
615
def fromOption[A](opt: Option[A]): Maybe[A]
616
617
/** Create from nullable value */
618
def fromNullable[A](a: A): Maybe[A]
619
}
620
```
621
622
### Cord
623
624
#### Cord
625
626
Efficient string-like data structure using ropes for O(1) concatenation.
627
628
```scala { .api }
629
case class Cord(toList: List[String]) {
630
/** Append another Cord */
631
def ++(other: Cord): Cord
632
633
/** Prepend a String */
634
def +:(s: String): Cord
635
636
/** Append a String */
637
def :+(s: String): Cord
638
639
/** Convert to String */
640
override def toString: String
641
642
/** Length in characters */
643
def length: Int
644
645
/** Check if empty */
646
def isEmpty: Boolean
647
648
/** Take first n characters */
649
def take(n: Int): Cord
650
651
/** Drop first n characters */
652
def drop(n: Int): Cord
653
}
654
655
object Cord {
656
/** Empty Cord */
657
val empty: Cord
658
659
/** Create from String */
660
def apply(s: String): Cord
661
662
/** Create from List of Strings */
663
def fromList(ss: List[String]): Cord
664
}
665
```