{"size": 7285, "ext": "scrbl", "max_stars_repo_path": "scribblings/algorithms.scrbl", "max_stars_repo_name": "filiplajszczak/racket-algorithms", "max_stars_repo_stars_event_min_datetime": "2020-05-17T18:37:16.000Z", "max_stars_repo_stars_event_max_datetime": "2021-12-06T14:32:27.000Z", "max_issues_repo_path": "scribblings/algorithms.scrbl", "max_issues_repo_name": "filiplajszczak/racket-algorithms", "max_issues_repo_issues_event_min_datetime": "2020-05-18T14:41:50.000Z", "max_issues_repo_issues_event_max_datetime": "2020-07-09T01:30:05.000Z", "max_forks_repo_path": "scribblings/algorithms.scrbl", "max_forks_repo_name": "filiplajszczak/racket-algorithms", "max_forks_repo_forks_event_min_datetime": "2021-10-24T23:58:41.000Z", "max_forks_repo_forks_event_max_datetime": "2021-12-04T21:50:19.000Z"}
{"max_stars_count": 3, "max_issues_count": 5, "max_forks_count": 2, "avg_line_length": 30.3541666667, "max_line_length": 119, "alphanum_fraction": 0.6573781743}
#lang scribble/manual
@(require (for-label racket
                     (only-in algorithms)))

@title{algorithms}
@author{Conor Hoekstra}

@defmodule[algorithms]

A package containing many useful algorithms (borrowed from many other programming languages).

@defproc[(adjacent-map [lst list?] [proc (-> any/c any/c any/c)]) (listof any/c)]{
@margin-note{This algorithm is similar to Haskell's
@hyperlink["https://hackage.haskell.org/package/utility-ht-0.0.15/docs/Data-List-HT.html#v:mapAdjacent"]{mapAdjacent}.}
Returns a list of elements after apply @racket[proc] to adjacent elements.

Examples:
@codeblock|{
  > (adjacent-map '(1 2 3 4 5 6) *)
  '(2 6 12 20 30)
  > (adjacent-map '(1 2 1 3 4 3) <)
  '(#t #f #t #t #f)
}|}

@defproc[(all? [lst (listof boolean?)]) (boolean?)]{
@margin-note{This algorithm is similar to Python's
@hyperlink["https://docs.python.org/3/library/functions.html#all"]{all}.}
Returns @racket[#t] if all the elements of @racket[lst] are @racket[#t], otherwise returns @racket[#f].

Examples:
@codeblock|{
  > (all? '(#t #t #t))
  #t
  > (all? '(#t #t #f))
  #f
}|}

@defproc[(any? [lst (listof boolean?)]) (boolean?)]{
@margin-note{This algorithm is similar to Python's
@hyperlink["https://docs.python.org/3/library/functions.html#any"]{any}.}
Returns @racket[#t] if any of the elements of @racket[lst] are @racket[#t], otherwise returns @racket[#f].

Examples:
@codeblock|{
  > (any? '(#f #t #f))
  #t
  > (any? '(#f #f #f))
  #f
}|}

@defproc[(chunks-of [lst list?] [k exact-nonnegative-integer?]) (listof list?)]{
@margin-note{This algorithms is the same as Haskell's
@hyperlink["https://hackage.haskell.org/package/split-0.2.3.4/docs/Data-List-Split.html#v:chunksOf"]{chunksOf}.}
Returns a list of lists of @racket[k] elements each.
Note that this is a specialization of @racket[sliding] where @racket[size] is equal to @racket[step].

Examples:
@codeblock|{
  > (chunks-of '(1 2 1 3 4 3) 2)
  '((1 2) (1 3) (4 3))
  > (chunks-of '(1 2 1 3 4 3) 3)
  '((1 2 1) (3 4 3))
}|}

@defproc[(generate [n exact-nonnegative-integer?] [proc (-> any/c)]) (listof any/c)]{
@margin-note{This algorithm is similar to C++'s
@hyperlink["https://en.cppreference.com/w/cpp/algorithm/generate"]{generate}.}
Returns a list of @racket[n] elements generated from invoking @racket[proc] @racket[n] times.

Examples:
@codeblock|{
  > (generate 3 *)
  '(1 1 1)
  > (generate 3 +)
  '(0 0 0)
}|}

@defproc[(increasing? [lst (listof real?)]) (boolean?)]{
Returns @racket[#t] if all the elements of @racket[lst] are strictly increasing,
otherwise returns @racket[#f].

Examples:
@codeblock|{
  > (increasing? '(1 2 3 4))
  #t
  > (increasing? '(1 2 3 5))
  #t
  > (increasing? '(1 2 2 3))
  #f
}|}

@defproc[(init [lst list?]) list?]{
@margin-note{This algorithm comes from Haskell's
@hyperlink["https://hackage.haskell.org/package/base-4.14.0.0/docs/Prelude.html#v:init"]{init}.}
Return all the elements of a list except the last one.

Examples:
@codeblock|{
  > (init '(1 2 3 4))
  '(1 2 3)
  > (init '((1 2) (3 4) (5 6)))
  '((1 2) (3 4))
}|}

@defproc[(product [lst (listof real?)]) real?]{
Returns the product of the elements in @racket[lst].

Examples:
@codeblock|{
  > (product '(1 2 3))
  6
  > (product '(1 2 3 4))
  24
}|}

@defproc[(repeat [n exact-nonnegative-integer?] [val integer?]) list?]{
@margin-note{This algorithms is the same as Clojures's
@hyperlink["https://clojuredocs.org/clojure.core/repeat"]{repeat} and D's
@hyperlink["https://dlang.org/library/std/range/repeat.html#0"]{repeat}.}
Returns a list of @racket[val] repeated @racket[n] times.

Examples:
@codeblock|{
  > (repeat 5 #t)
  '(#t #t #t #t #t)
  > (repeat 5 '())
  '(() () () () ())
}|}

@defproc[(scanl [lst list?]) list?]{
@margin-note{This algorithm originally comes from APL's monadic
@hyperlink["http://microapl.com/apl_help/ch_020_020_820.htm"]{\ scan} operator. It is more similar to Haskell's
@hyperlink["https://hackage.haskell.org/package/base-4.14.0.0/docs/Prelude.html#v:scanl1"]{scanl1} however.}
@racket[scanl] is similar to @racket[foldl], but returns a list of successive reduced values from the left.

Examples:
@codeblock|{
  > (scanl + '(1 2 3 4))
  '(1 3 6 10)
  > (scanl * '(1 2 3 4))
  '(1 2 6 24)
}|}

@defproc[(scanr [lst list?]) list?]{
@margin-note{This algorithm originally comes from APL's monadic
@hyperlink["http://microapl.com/apl_help/ch_020_020_820.htm"]{\ scan} operator. It is more similar to Haskell's
@hyperlink["https://hackage.haskell.org/package/base-4.14.0.0/docs/Prelude.html#v:scanr1"]{scanr1} however.}
@racket[scanr] is similar to @racket[foldr], but returns a list of successive reduced values from the right.

Examples:
@codeblock|{
  > (scanr + '(1 2 3 4))
  '(10 9 7 4)
  > (scanr * '(1 2 3 4))
  '(24 24 12 4)
}|}

@defproc[(sliding [lst list?] [size exact-nonnegative-integer?] [step exact-nonnegative-integer? 1]) (listof list?)]{
@margin-note{This algorithms is the same as Haskell's
@hyperlink["https://hackage.haskell.org/package/split-0.2.3.4/docs/Data-List-Split.html#v:divvy"]{divvy}, Clojure's
@hyperlink["https://clojuredocs.org/clojure.core/partition"]{partition} and D's
@hyperlink["https://dlang.org/library/std/range/slide.html"]{slide}.}
Returns a list of lists of @racket[size] elements each, at offset @racket[step] apart.

Examples:
@codeblock|{
  > (sliding '(1 2 3 4) 2)
  '((1 2) (2 3) (3 4))
  > (sliding '(1 2 3 4 5) 2 3)
  '((1 2) (4 5))
}|}

@defproc[(sorted? [lst list?]) (boolean?)]{
@margin-note{This algorithm is similar to C++'s
@hyperlink["https://en.cppreference.com/w/cpp/algorithm/is_sorted"]{std::is_sorted}.}
Returns @racket[#t] if all the elements of @racket[lst] are in sorted order, otherwise returns @racket[#f].

Examples:
@codeblock|{
  > (sorted? '(1 2 3 4))
  #t
  > (sorted? '(1 2 3 3))
  #t
  > (sorted? '(1 2 3 2))
  #f
}|}

@defproc[(sum [lst (listof real?)]) real?]{
Returns the sum of the elements in @racket[lst].

Examples:
@codeblock|{
  > (sum '(1 2 3 4))
  10
  > (sum '())
  0
}|}

@defproc[(tail [lst list?]) list?]{
@margin-note{This algorithm comes from Haskell's
@hyperlink["https://hackage.haskell.org/package/base-4.14.0.0/docs/Prelude.html#v:tail"]{tail}.}
Return all the elements of a list except the first one. 
    
Note: this is the same as Racket's @racket[cdr] and @racket[rest] and therefore isn't really necessary.

Examples:
@codeblock|{
  > (tail '(1 2 3))
  '(2 3)
  > (tail '(1))
  '()
}|}

@defproc[(zip [lst list?] [lst2 list?]) (listof list?)]{
@margin-note{This algorithm is similar to Haskell's
@hyperlink["https://hackage.haskell.org/package/base-4.14.0.0/docs/Prelude.html#v:zip"]{zip}.}
Returns a list of corresponding pairs when given two lists.

Examples:
@codeblock|{
  > (zip '(1 2 3) '(4 5 6))
  '((1 4) (2 5) (3 6))
  > (zip '() '())
  '()
}|}

@defproc[(zip-with [proc (-> any/c ... any/c)] [lst list?] ...) (listof any/c)]{
@margin-note{This algorithm is similar to Haskell's
@hyperlink["https://hackage.haskell.org/package/base-4.14.0.0/docs/Prelude.html#v:zipWith"]{zipWith}.}
Returns a list after zipping together the variadic number of @racket[lst]s and applying @racket[proc]
to each of the "zipped together" elements.

Examples:
@codeblock|{
  > (zip-with + '(1 2 3) '(4 5 6))
  '(5 7 9)
  > (zip-with + '(1 2 3) '(4 5 6) '(7 8 9))
  '(12 15 18)
}|}
