Purity project

This project contains realisations of common-used math functions and classical algorithms, written in Scala's pure-functional style.

Some of them are a new sight at Scala's standard library, some are persistent data structures, some are completely new functions.

The main purpose of this library is to spread ideas of a functional programming in Scala and to challenge yourself by creating classical imperative algorithms in a new way.

Would be great, if you contribute, in case that presented algorithms are not as effective as they can be, and you know how to fix this, or if you have ideas, that can be added in the future.

Current list of supported algorithms:

Sorting algorithms:

1. Quick sort sortingAlgorithms/QuickSort

2. Bogosort sortingAlgorithms/unseriousAlgorithms/Bogosort

3. Sleep sort sortingAlgorithms/unseriousAlgorithms/SleepSort

4. Bubble sort sortingAlgorithms/BubbleSort

5. Merge sort sortingAlgorithms/MergeSort

6. Insertion sort sortingAlgorithms/InsertionSort

7. Selection sort sortingAlgorithms.SelectionSort

8. Heap sort sortingAlgorithms.HeapSort

Persistent data structures:

1. LinkedList dataStructures.LinkedList

2. Queue dataStructures.Queue

3. Stack dataStructures.Stack

4. Set dataStructures.Set

5. Binary tree dataStructures.BinaryTree

6. Heap dataStructures.Heap

7. Red-Black Tree dataStructures.RedBlackTree

Lambda calculus basics:

1. Polymorphic lambda calculus lambdaCalculus/PolymorphicLambdaCalculus

2. Pure Lambda Calculus PureLambdaCalculus.scala lambdaCalculus/PureLambdaCalculus

Integer operations:

integerOperations.IntegerProperties

1. .isOdd

2. .isEven

3. .isSquared

4. .sumOfDigits

5. .compositionOfDigits

6. .numOfDigits

7. .divisors

8. .nthGreatestDivisor(n)

9. .numOfDivisors

10. .sumOfDivisors

11. .isPrime, works with O(sqrt(n)) speed

12. .isPrimeFermat(). works with O(log(n)) speed

13. .sqr

14. .powN()

15. .gcdWith(secondInt)

16. .isPrimeFermatStrict (does not fail on Carmichael numbers, works slowly)

17. .isPrimeFermatFast (does not fail on Carmichael numbers, works fast, only with Ints)

18. .lcmWith(secondInt)

19. Factorial (!)

20. Double factorial (!!)

21. Convolution of a number (127 -> 1+2+7 -> 10 -> 1+0 -> 1)

Additional Integers math:

integerOperations.IntegerMath

1. .isFreeOfSquares

2. .isCarmichael

3. .isLuc_Carmichael

4. .isFibonacci

5. .nthCatalan

6. .binaryPower(), works with O(log(n)) speed

7. .isZuckerman

8. .isHarshad

9. .gcdExtendedWith()

Integer lists generators:

integerOperations.IntegerGenerators

1. Arithmetic regression

2. Arithmetic progression

3. Squares until N

4. Divisors of N

5. Binary divisors of N

6. Divisors, multiple by N

7. Prime divisors

8. Carmichael numbers

9. Luc-Carmichael numbers

10. Fibonacci numbers

11. Random ints

12. Catalan numbers

Additional math generators:

integerOperations.IntegerGeneratorsMath

1. Fermat numbers

2. Eratosthenes primes sieve O(log(log(n)))

Char operations:

charOperations.CharProperties

1. .isVowel

2. .isConsonant

Double operations:

doubleOperations.DoubleProperties

1. .inverse

2. .sqrDouble

3. .abs

4. .toDegrees

5. .incDouble

List/values operations:

listOperations

1. get(List[A], index)

2. isPalindrome(List[A])

3. isPalindrome([A])

4. Counter for the number of sign changes in a list of integers

5. Counter for the number of letter changes from vowel to consonant in a list of integers

6. .isSorted

7. binary search in a list

8. linear search in a list

9. permutations(List[A], len)

Basic combinatorics:

combinatorics

1. permutationsCount

2. accomodations

3. combinations

4. accomodations with repeats

5. combinations with repeats

Encoders:

1. RLE cryptographyOperations.encoders.RLE_Encoder

2. Huffman cryptographyOperations.encoders.HuffmanEncoder

3. Gray cryptographyOperations.encoders.GrayEncoder

4. Morse cryptographyOperations.encoders.MorseEncoder

Decoders:

1. RLE functionalAlgorithms.decoders.RLE_Decoder

2. Huffman functionalAlgorithms.decoders.HuffmanDecoder

3. Gray functionalAlgorithms.decoders.GrayDecoder

4. Morse functionalAlgorithms.decoders.MorseDecoder

Additional arithmetics:

1. Rational numbers additionalArithmetics.Rational

2. Complex numbers complexOperations.Complex

Useful asynchronous functions with Futures:

asynchronous.UsefulFuture

1. .bypassOnComplete()

2. .ifFailure()

3. .result

4. .completeAndThen()

5. .completeAndThenComplete()

Useful asynchronous functions with Option:

asynchronous.UsefulOption

1. .getOrZero

2. .getOrZeroL

3. .getOrThrow

4. .getOrEmpty

5. .getOrMax

Math constants:

MathConstants

1. Pi

2. Tau

3. E

4. Pythagoras constant

5. Theodorus constant

6. Gamma

7. Phi

8. Plastic number

Time operations:

time.Time

1. Conversions of hours, seconds and minutes.

Planned:

1. Operations with double

Some sources, that were used via development:

0. Martin Odersky's "Functional Programming in Scala Specialization "https://www.coursera.org/specializations/scala" (English)

1. Chris Okasaki's "Purely Functional Data Structures" (English)

2. Richard Bird's "Pearls of Functional Algorithm Design" (English)

3. Denis Shevchenko's "About Haskell in a human way": https://www.ohaskell.guide (Russian)

4. Louis Botterill's mostly software and techy Blog: http://louisbotterill.blogspot.ru (English)

5. Alvin Alexander's scala blog: https://alvinalexander.com (English)

6. Richard G.E. Pinch "The Carmichael numbers up to 10^18" https://arxiv.org/pdf/math/0604376v1.pdf (English)

7. Site about algorithms http://e-maxx.ru (Russian/English)

8. "Rosetta code" website about algorithms: https://rosettacode.org/wiki/Rosetta_Code (English)

9. Vladimir Kostykov's Scala algorithms library: https://github.com/vkostyukov/scalacaster (English)

10. Raul Rojas's "A Tutorial Introduction to the Lambda Calculus": http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf (English)

11. ITMO University's wiki: https://neerc.ifmo.ru/wiki/index.php?title=Лямбда-исчисление (Russian)