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         if !result {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         for !closed(c) {
  94                 <- c
  95                 len++
  96         }
  97         return len - 1
  98 }
  99
 100 func (s Sequence) Output(c chan Element) {
 101         for el := range s() {
 102                 c <- el
 103         }
 104 }
 105
 106 func Upto(limit int) Sequence {
 107         return Seq(func(c SeqChan) {
 108                 for i := 0; i < limit; i++ {
 109                         c <- i
 110                 }
 111         })
 112 }
 113
 114 func (s Sequence) Filter(filter func(e Element)bool) Sequence {
 115         return Seq(func(c SeqChan){
 116                 for el := range s() {
 117                         if filter(el) {
 118                                 c <- el
 119                         }
 120                 }
 121         })
 122 }
 123
 124 func (s Sequence) Do(f func(el Element)) {
 125         for v := range s() {
 126                 f(v)
 127         }
 128 }
 129
 130 func (s Sequence) Map(f func(i Element)Element) Sequence {
 131         return Seq(func(c SeqChan) {
 132                 for v := range s() {
 133                         c <- f(v)
 134                 }
 135         })
 136 }
 137
 138 func (s Sequence) FlatMap(f func(i Element) Sequence) Sequence {
 139         return Seq(func(c SeqChan) {
 140                 for v := range s() {
 141                         for sub := range f(v)() {
 142                                 c <- sub
 143                         }
 144                 }
 145         })
 146 }
 147
 148 func (s Sequence) Fold(init Element, f func(acc, el Element)Element) Element {
 149         for el := range s() {
 150                 init = f(init, el)
 151         }
 152         return init
 153 }
 154
 155 //maybe convert this to use an accumulator instead of append?
 156 func (s Sequence) Combinations(number int) Sequence {
 157         if number == 0 || s.IsEmpty() {return From(From())}
 158         return s.Rest().Combinations(number - 1).Map(func(el Element)Element{
 159                 return el.(Sequence).AddFirst(s.First())
 160         }).Append(s.Rest().Combinations(number))
 161 }
 162
 163 //returns the product of the Sequences contained in sequences
 164 func (sequences Sequence) Product() Sequence {
 165         return sequences.Fold(From(From()), func(acc, el Element)Element{
 166                 return el.(Sequence).peelOnto(acc.(Sequence))
 167         }).(Sequence)
 168 }
 169
 170 func (s Sequence) peelOnto(seq Sequence) Sequence {
 171         return seq.FlatMap(func(old Element)Sequence{
 172                 return s.Map(func(i Element) Element {
 173                         return old.(Sequence).Append(From(i))
 174                 })
 175         })
 176 }
 177
 178 func (s Sequence) Reify() Sequence {
 179         vec := vector.Vector(make([]interface{}, 0, 128))
 180         for v := range s() {
 181                 sv, is := v.(Sequence)
 182                 if is {
 183                         vec.Push(sv.Reify())
 184                 } else {
 185                         vec.Push(v)
 186                 }
 187         }
 188         return From([]interface{}(vec)...)
 189 }
 190
 191 func (s Sequence) Prettyln(names map[Element]string, writer... io.Writer) {
 192         if len(writer) == 0 {
 193                 writer = []io.Writer{os.Stdout}
 194         }
 195         s.Pretty(names, writer...)
 196         fmt.Fprintln(writer[0])
 197 }
 198 func (s Sequence) Pretty(names map[Element]string, writer... io.Writer) {
 199         if len(writer) == 0 {
 200                 writer = []io.Writer{os.Stdout}
 201         }
 202         s.prettyLevel(0, names, writer[0])
 203 }
 204
 205 //This is pretty ugly :)
 206 func (s Sequence) prettyLevel(level int, names map[Element]string, w io.Writer) {
 207         name, hasName := names[s]
 208         if hasName {
 209                 fmt.Fprint(w, name)
 210         } else {
 211                 c := s()
 212                 fmt.Fprintf(w, "%*s%s", level, "", "[")
 213                 first := true
 214                 innerSeq := false
 215                 named := false
 216                 for v := range c {
 217                         _, named = names[v]
 218                         _,innerSeq = v.(Sequence)
 219                         if first {
 220                                 first = false
 221                                 if !named && innerSeq {
 222                                         fmt.Fprintln(w)
 223                                 }
 224                         } else if !named && innerSeq {
 225                                 fmt.Fprintln(w, ",")
 226                         } else {
 227                                 fmt.Fprint(w, ", ")
 228                         }
 229                         if innerSeq {
 230                                 v.(Sequence).prettyLevel(level + 4, names, w)
 231                         } else {
 232                                 fmt.Fprintf(w, "%v", v)
 233                         }
 234                 }
 235                 if innerSeq {
 236                         if !named {
 237                                 fmt.Fprintf(w, "\n%*s", level, "")
 238                         }
 239                 }
 240                 fmt.Fprintf(w, "]")
 241         }
 242 }