seq/seq.go

   1 // Copyright 2010 Bill Burdick. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4 //
   5 package seq
   6
   7 import "fmt"
   8 import "io"
   9 import "os"
  10 import "container/vector"
  11
  12 type Element interface{}
  13 type SeqChan chan Element
  14 type Sequence func()SeqChan
  15
  16 func IsSeq(s interface{}) bool {
  17         _, test := s.(Sequence)
  18         return test
  19 }
  20
  21 // f must behave properly when the channel is closed, so that IsEmpty and First work properly
  22 func Seq(f func(c SeqChan)) Sequence {
  23         return func() SeqChan {
  24                 c := make(SeqChan)
  25                 go func() {
  26                         defer close(c)
  27                         f(c)
  28                 }()
  29                 return c
  30         }
  31 }
  32
  33 func From(el... interface{}) Sequence {
  34         return Seq(func(c SeqChan) {Output(c, el...)})
  35 }
  36
  37 func Output(c SeqChan, el... interface{}) {
  38         for _, v := range el {
  39                 c <- v
  40         }
  41 }
  42
  43 func (s Sequence) First() Element {
  44         c := s()
  45         defer close(c)
  46         return <- c
  47 }
  48
  49 func (s Sequence) Rest() Sequence {
  50         return func()SeqChan{
  51                 c := s()
  52                 <- c
  53                 return c
  54         }
  55 }
  56
  57 func (s Sequence) AddFirst(els... interface{}) Sequence {
  58         return Seq(func(c SeqChan){
  59                 for el := range els {
  60                         c <- el
  61                 }
  62                 s.Output(c)
  63         })
  64 }
  65
  66 func (s Sequence) AddLast(els... interface{}) Sequence {
  67         return Seq(func(c SeqChan){
  68                 s.Output(c)
  69                 for el := range els {
  70                         c <- el
  71                 }
  72         })
  73 }
  74
  75 func (s Sequence) IsEmpty() bool {
  76         c := s()
  77         <- c
  78         result := closed(c)
  79         defer close(c)
  80         return result
  81 }
  82
  83 func (s Sequence) Append(s2 Sequence) Sequence {
  84         return Seq(func(c SeqChan){
  85                 s.Output(c)
  86                 s2.Output(c)
  87         })
  88 }
  89
  90 func (s Sequence) Len() int {
  91         len := 0
  92         c := s()
  93         defer close(c)
  94         for !closed(c) {
  95                 <- c
  96                 len++
  97         }
  98         return len - 1
  99 }
 100
 101 func (s Sequence) Output(c chan Element) {
 102         for el := range s() {
 103                 c <- el
 104         }
 105 }
 106
 107 func Upto(limit int) Sequence {
 108         return Seq(func(c SeqChan) {
 109                 for i := 0; i < limit; i++ {
 110                         c <- i
 111                 }
 112         })
 113 }
 114
 115 func (s Sequence) Filter(filter func(e Element)bool) Sequence {
 116         return Seq(func(c SeqChan){
 117                 for el := range s() {
 118                         if filter(el) {
 119                                 c <- el
 120                         }
 121                 }
 122         })
 123 }
 124
 125 func (s Sequence) Do(f func(el Element)) {
 126         for v := range s() {
 127                 f(v)
 128         }
 129 }
 130
 131 func (s Sequence) Map(f func(i Element)Element) Sequence {
 132         return Seq(func(c SeqChan) {
 133                 for v := range s() {
 134                         c <- f(v)
 135                 }
 136         })
 137 }
 138
 139 func (s Sequence) FlatMap(f func(i Element) Sequence) Sequence {
 140         return Seq(func(c SeqChan) {
 141                 for v := range s() {
 142                         for sub := range f(v)() {
 143                                 c <- sub
 144                         }
 145                 }
 146         })
 147 }
 148
 149 func (s Sequence) Fold(init Element, f func(acc, el Element)Element) Element {
 150         for el := range s() {
 151                 init = f(init, el)
 152         }
 153         return init
 154 }
 155
 156 //maybe convert this to use an accumulator instead of append?
 157 func (s Sequence) Combinations(number int) Sequence {
 158         if number == 0 || s.IsEmpty() {return From(From())}
 159         return s.Rest().Combinations(number - 1).Map(func(el Element)Element{
 160                 return el.(Sequence).AddFirst(s.First())
 161         }).Append(s.Rest().Combinations(number))
 162 }
 163
 164 //returns the product of the Sequences contained in sequences
 165 func (sequences Sequence) Product() Sequence {
 166         return sequences.Fold(From(From()), func(acc, el Element)Element{
 167                 return el.(Sequence).peelOnto(acc.(Sequence))
 168         }).(Sequence)
 169 }
 170
 171 func (s Sequence) peelOnto(seq Sequence) Sequence {
 172         return seq.FlatMap(func(old Element)Sequence{
 173                 return s.Map(func(i Element) Element {
 174                         return old.(Sequence).Append(From(i))
 175                 })
 176         })
 177 }
 178
 179 func (s Sequence) Reify() Sequence {
 180         vec := vector.Vector(make([]interface{}, 0, 128))
 181         for v := range s() {
 182                 sv, is := v.(Sequence)
 183                 if is {
 184                         vec.Push(sv.Reify())
 185                 } else {
 186                         vec.Push(v)
 187                 }
 188         }
 189         return From([]interface{}(vec)...)
 190 }
 191
 192 func (s Sequence) ToVector() Vector {
 193         vec := vector.Vector(make([]interface{}, 0, 128))
 194         for v := range s() {
 195                 sv, is := v.(Sequence)
 196                 if is {
 197                         vec.Push(sv.ToVector())
 198                 } else {
 199                         vec.Push(v)
 200                 }
 201         }
 202         return vec
 203 }
 204
 205 func (s Sequence) Prettyln(names map[Element]string, writer... io.Writer) {
 206         if len(writer) == 0 {
 207                 writer = []io.Writer{os.Stdout}
 208         }
 209         s.Pretty(names, writer...)
 210         fmt.Fprintln(writer[0])
 211 }
 212 func (s Sequence) Pretty(names map[Element]string, writer... io.Writer) {
 213         if len(writer) == 0 {
 214                 writer = []io.Writer{os.Stdout}
 215         }
 216         s.prettyLevel(0, names, writer[0])
 217 }
 218
 219 //This is pretty ugly :)
 220 func (s Sequence) prettyLevel(level int, names map[Element]string, w io.Writer) {
 221         name, hasName := names[s]
 222         if hasName {
 223                 fmt.Fprint(w, name)
 224         } else {
 225                 c := s()
 226                 fmt.Fprintf(w, "%*s%s", level, "", "[")
 227                 first := true
 228                 innerSeq := false
 229                 named := false
 230                 for v := range c {
 231                         _, named = names[v]
 232                         _,innerSeq = v.(Sequence)
 233                         if first {
 234                                 first = false
 235                                 if !named && innerSeq {
 236                                         fmt.Fprintln(w)
 237                                 }
 238                         } else if !named && innerSeq {
 239                                 fmt.Fprintln(w, ",")
 240                         } else {
 241                                 fmt.Fprint(w, ", ")
 242                         }
 243                         if innerSeq {
 244                                 v.(Sequence).prettyLevel(level + 4, names, w)
 245                         } else {
 246                                 fmt.Fprintf(w, "%v", v)
 247                         }
 248                 }
 249                 if innerSeq {
 250                         if !named {
 251                                 fmt.Fprintf(w, "\n%*s", level, "")
 252                         }
 253                 }
 254                 fmt.Fprintf(w, "]")
 255         }
 256 }