forked from scalaz/scalaz
-
Notifications
You must be signed in to change notification settings - Fork 0
/
NonEmptyList.scala
191 lines (141 loc) · 6.09 KB
/
NonEmptyList.scala
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
package scalaz
/** A singly-linked list that is guaranteed to be non-empty. */
final class NonEmptyList[+A] private[scalaz](val head: A, val tail: List[A]) {
import NonEmptyList._
import Zipper._
def <::[AA >: A](b: AA): NonEmptyList[AA] = nel(b, head :: tail)
def <:::[AA >: A](bs: List[AA]): NonEmptyList[AA] = bs match {
case Nil => this
case b :: bs => nel(b, bs ::: list)
}
def :::>[AA >: A](bs: List[AA]): NonEmptyList[AA] = nel(head, tail ::: bs)
/** Append one nonempty list to another. */
def append[AA >: A](f2: NonEmptyList[AA]): NonEmptyList[AA] = list <::: f2
def map[B](f: A => B): NonEmptyList[B] = nel(f(head), tail.map(f))
/** @since 7.0.3 */
def foreach(f: A => Unit): Unit = {
f(head)
tail foreach f
}
import collection.mutable.ListBuffer
def flatMap[B](f: A => NonEmptyList[B]): NonEmptyList[B] = {
val b = new ListBuffer[B]
val p = f(head)
b += p.head
b ++= p.tail
tail.foreach {
a =>
val p = f(a)
b += p.head
b ++= p.tail
}
val bb = b.toList
nel(bb.head, bb.tail)
}
def traverse1[F[_], B](f: A => F[B])(implicit F: Apply[F]): F[NonEmptyList[B]] = tail match {
case Nil => F.map(f(head))(nel(_, Nil))
case b :: bs => F.apply2(f(head), nel(b, bs).traverse1(f)) {
case (h, t) => nel(h, t.head :: t.tail)
}
}
def list: List[A] = head :: tail
def stream: Stream[A] = head #:: tail.toStream
def toZipper: Zipper[A] = zipper(Stream.Empty, head, tail.toStream)
def zipperEnd: Zipper[A] = {
import Stream._
tail.reverse match {
case Nil => zipper(empty, head, empty)
case t :: ts => zipper(ts.toStream :+ head, t, empty)
}
}
/** @since 7.0.2 */
def init: List[A] = if(tail.isEmpty) Nil else (head :: tail.init)
/** @since 7.0.2 */
def last: A = if(tail.isEmpty) head else tail.last
def tails: NonEmptyList[NonEmptyList[A]] = nel(this, tail match {
case Nil => Nil
case h :: t => nel(h, t).tails.list
})
def reverse: NonEmptyList[A] = (list.reverse: @unchecked) match {
case x :: xs => nel(x, xs)
}
/** @since 7.0.2 */
def sortBy[B](f: A => B)(implicit o: Order[B]): NonEmptyList[A] = (list.sortBy(f)(o.toScalaOrdering): @unchecked) match {
case x :: xs => nel(x, xs)
}
/** @since 7.0.2 */
def sortWith(lt: (A, A) => Boolean): NonEmptyList[A] = (list.sortWith(lt): @unchecked) match {
case x :: xs => nel(x, xs)
}
/** @since 7.0.2 */
def sorted[B >: A](implicit o: Order[B]): NonEmptyList[A] = (list.sorted(o.toScalaOrdering): @unchecked) match {
case x :: xs => nel(x, xs)
}
def size: Int = 1 + tail.size
def zip[B](b: => NonEmptyList[B]): NonEmptyList[(A, B)] =
nel((head, b.head), tail zip b.tail)
def unzip[X, Y](implicit ev: A <:< (X, Y)): (NonEmptyList[X], NonEmptyList[Y]) = {
val (a, b) = head: (X, Y)
val (aa, bb) = tail.unzip: (List[X], List[Y])
(nel(a, aa), nel(b, bb))
}
override def toString: String = "NonEmpty" + (head :: tail)
override def equals(any: Any): Boolean =
any match {
case that: NonEmptyList[_] => this.list == that.list
case _ => false
}
override def hashCode: Int =
list.hashCode
}
object NonEmptyList extends NonEmptyListInstances with NonEmptyListFunctions {
def apply[A](h: A, t: A*): NonEmptyList[A] =
nels(h, t: _*)
def unapplySeq[A](v: NonEmptyList[A]): Option[(A, List[A])] =
Some((v.head, v.tail))
}
sealed abstract class NonEmptyListInstances0 {
implicit def nonEmptyListEqual[A: Equal]: Equal[NonEmptyList[A]] = Equal.equalBy[NonEmptyList[A], List[A]](_.list)(std.list.listEqual[A])
}
sealed abstract class NonEmptyListInstances extends NonEmptyListInstances0 {
implicit val nonEmptyList =
new Traverse1[NonEmptyList] with Monad[NonEmptyList] with Plus[NonEmptyList] with Comonad[NonEmptyList] with Each[NonEmptyList] with Zip[NonEmptyList] with Unzip[NonEmptyList] with Length[NonEmptyList] {
def traverse1Impl[G[_] : Apply, A, B](fa: NonEmptyList[A])(f: A => G[B]): G[NonEmptyList[B]] =
fa traverse1 f
override def foldMapRight1[A, B](fa: NonEmptyList[A])(z: A => B)(f: (A, => B) => B): B = {
val reversed = fa.reverse
reversed.tail.foldLeft(z(reversed.head))((x, y) => f(y, x))
}
override def foldMapLeft1[A, B](fa: NonEmptyList[A])(z: A => B)(f: (B, A) => B): B =
fa.tail.foldLeft(z(fa.head))(f)
override def foldMap1[A, B](fa: NonEmptyList[A])(f: A => B)(implicit F: Semigroup[B]): B = {
fa.tail.foldLeft(f(fa.head))((x, y) => F.append(x, f(y)))
}
// would otherwise use traverse1Impl
override def foldLeft[A, B](fa: NonEmptyList[A], z: B)(f: (B, A) => B): B =
fa.tail.foldLeft(f(z, fa.head))(f)
def bind[A, B](fa: NonEmptyList[A])(f: A => NonEmptyList[B]): NonEmptyList[B] = fa flatMap f
def point[A](a: => A): NonEmptyList[A] = NonEmptyList(a)
def plus[A](a: NonEmptyList[A], b: => NonEmptyList[A]): NonEmptyList[A] = a.list <::: b
def copoint[A](p: NonEmptyList[A]): A = p.head
def cobind[A, B](fa: NonEmptyList[A])(f: NonEmptyList[A] => B): NonEmptyList[B] = map(cojoin(fa))(f)
override def cojoin[A](a: NonEmptyList[A]): NonEmptyList[NonEmptyList[A]] = a.tails
def each[A](fa: NonEmptyList[A])(f: A => Unit) = fa.list foreach f
def zip[A, B](a: => NonEmptyList[A], b: => NonEmptyList[B]) = a zip b
def unzip[A, B](a: NonEmptyList[(A, B)]) = a.unzip
override def length[A](a: NonEmptyList[A]): Int = a.size
}
implicit def nonEmptyListSemigroup[A]: Semigroup[NonEmptyList[A]] = new Semigroup[NonEmptyList[A]] {
def append(f1: NonEmptyList[A], f2: => NonEmptyList[A]) = f1 append f2
}
implicit def nonEmptyListShow[A: Show]: Show[NonEmptyList[A]] =
Contravariant[Show].contramap(std.list.listShow[A])(_.list)
implicit def nonEmptyListOrder[A: Order]: Order[NonEmptyList[A]] =
Order.orderBy[NonEmptyList[A], List[A]](_.list)(std.list.listOrder[A])
}
trait NonEmptyListFunctions {
def nel[A](h: A, t: List[A]): NonEmptyList[A] =
new NonEmptyList(h, t)
def nels[A](h: A, t: A*): NonEmptyList[A] =
nel(h, t.toList)
}