blrobin2 · June 12, 2022 09:26 · nickx720 · Oct 28, 2020 · andelkocvjetkovic · Jun 12, 2022
diff --git a/ord-sorts.js b/ord-sorts.js
 // A demonstration of sorting objects with Ord instances
 // equals :: Setoid a => a ~> a -> Boolean
 // lte :: Ord a => a ~> a -> Boolean

 /*
 * Data Constructors, and their Setoid and Ord instances
 */

 // I'm using the daggy library to make constructors https://github.com/fantasyland/daggy
 const daggy = require('daggy')

 //- A coordinate in 3D space
 //+ Coord :: (Int, Int, Int) -> Coord
 const Coord = daggy.tagged('Coord', ['x', 'y', 'z'])

 //- Setoid instance for Coord (prequisite for Ord)
 //+ equals :: Coord ~> Coord -> Boolean
 Coord.prototype.equals = function coordEquals(that) {
  return this.x == that.x
    && this.y == that.y
    && this.z == that.z
 }

 //- Ord instance for Coord
 //+ lte :: Coord ~> Coord -> Boolean
 Coord.prototype.lte = function coordLte(that) {
  return (this.x < that.x)
    || (this.x == that.x && this.y < that.y)
    || (this.x == that.x && this.y == that.y && this.z < that.z)
    || (this.equals(that))
 }

 //- A line between two coordinates
 //+ Line :: (Coord, Coord) -> Line
 const Line = daggy.tagged('Coord', ['from', 'to'])

 //- Setoid instance for Line (prequisite for Ord)
 //+ equals :: Line ~> Line -> Boolean
 Line.prototype.equals = function lineEquals(that) {
  return this.from.equals(that.from)
    && this.to.equals(that.to)
 }

 //- Ord instance of Line
 //+ lte :: Line ~> Line -> Boolean
 Line.prototype.lte = function lineLte(that) {
  return (lt(this.from, that.from))
    || (this.from.equals(that.from) && lt(this.to, that.to))
    || (this.equals(that))
 }

 // Derived Ord operations
 // With `lte` and `equals` we can derive all the other Ord operations we want

 // lte :: Ord a => a -> a -> Boolean
 const lte = function ordLte(x, y) {
  return x.lte(y)
 }

 // Greater than. The OPPOSITE of lte.
 // gt :: Ord a => a -> a -> Boolean
 const gt = function ordGt(x, y) {
  return !lte(x, y)
 }

 // Greater than OR equals
 // gte :: Ord a => a -> a -> Boolean
 const gte = function ordGte(x, y) {
  return gt(x, y) || x.equals(y)
 }

 // Less than. The OPPOSITE of gte
 // lt :: Ord a => a -> a -> Boolean
 const lt = function ordLt(x, y) {
  return !gte(x, y)
 }

 /*
 * Sorts
 * - Each make copies rather than modifying list in place
 */
 const copy = xs => [...xs]

 //- Sort a list of Ords using bubble sort algorithm
 // bubbleSort :: Ord a => [a] -> [a]
 const bubbleSort = xs_ => {
  const xs = copy(xs_)
  let n = xs.length - 1
  let swapped = true
  while (swapped) {
    swapped = false
    for (let i = 1; i <= n; i++) {
      const curr = xs[i]
      const prev = xs[i - 1]
      if (gt(prev, curr)) {
        xs[i - 1] = curr
        xs[i] = prev
        swapped = true
      }
    }
  }
  return xs
 }

 //- Sort a list of Ords using merge sort algorithm
 //+ mergeSort :: Ord a => [a] -> [a]
 const mergeSort = m => {
  if (m.length <= 1) return m

  const left = []
  const right = []
  m.forEach((x, i) => {
    if (i < (m.length / 2)) {
      left.push(x)
    } else {
      right.push(x)
    }
  })

  const leftSorted = mergeSort(left)
  const rightSorted = mergeSort(right)

  return _merge(leftSorted, rightSorted)
 }

 const _merge = (left, right) => {
  const result = []
  let l = copy(left)
  let r = copy(right)

  while (l.length > 0 && r.length > 0) {
    const [lhead, ...ltail] = l
    const [rhead, ...rtail] = r

    if (lte(lhead, rhead)) {
      result.push(lhead)
      l = ltail
    } else {
      result.push(rhead)
      r = rtail
    }
  }

  // Either left or right may have elements left; consume them
  // (Only one of the following loops will actually be entered)
  if (l.length > 0) {
    result.push(...l)
  }
  if (r.length > 0) {
    result.push(...r)
  }

  return result
 }

 //- Sort a list of Ords using quicksort algorithm
 //+ quickSort :: Ord a => [a] -> [a]
 const quickSort = xs => _quickSort(copy(xs), 0, xs.length - 1)

 const _quickSort = (xs, lo, hi) => {
  if (lo < hi) {
    const p = _partition(xs, lo, hi)
    _quickSort(xs, lo, p - 1)
    _quickSort(xs, p + 1, hi)
  }
  return xs
 }

 const _partition = (xs, lo, hi) => {
  const pivot = xs[hi]
  let i = lo
  for (let j = lo; j < hi; j++) {
    if (lt(xs[j], pivot)) {
      if (i != j) {
        const xsi = xs[i]
        const xsj = xs[j]
        xs[i] = xsj
        xs[j] = xsi
      }
      i++
    }
  }
  const xsi = xs[i]
  const xshi = xs[hi]
  xs[i] = xshi
  xs[hi] = xsi
  return i
 }


 /*
 * Demonstrations
 */

 const coord_list = [
  Coord(1, 2, 3),
  Coord(1, 2, 1),
  Coord(1, 1, 2)
 ]

 const line_list = [
  Line (
    origin,
    Coord(1, 2, 3)
  ),
  Line (
    Coord(1, 2, 1),
    Coord(1, 2, 2),
  ),
  Line(
    origin,
    Coord(1, 1, 2)
  )
 ]

 // bubbleSort(coord_list)
 // mergeSort(coord_list)
 // quickSort(coord_list)
 // -> [
 //  { x: 1, y: 1, z: 2 },
 //  { x: 1, y: 2, z: 1 },
 //  { x: 1, y: 2, z: 3 }
 // ]

 // bubbleSort(line_list)
 // mergeSort(line_list)
 // quickSort(line_list)
 // -> [ 
 //  { from: { x: 0, y: 0, z: 0 }, to: { x: 1, y: 1, z: 2 } },
 //  { from: { x: 0, y: 0, z: 0 }, to: { x: 1, y: 2, z: 3 } },
 //  { from: { x: 1, y: 2, z: 1 }, to: { x: 1, y: 2, z: 2 } }
 // ]
	// A demonstration of sorting objects with Ord instances
	// equals :: Setoid a => a ~> a -> Boolean
	// lte :: Ord a => a ~> a -> Boolean

	/*
	* Data Constructors, and their Setoid and Ord instances
	*/

	// I'm using the daggy library to make constructors https://github.com/fantasyland/daggy
	const daggy = require('daggy')

	//- A coordinate in 3D space
	//+ Coord :: (Int, Int, Int) -> Coord
	const Coord = daggy.tagged('Coord', ['x', 'y', 'z'])

	//- Setoid instance for Coord (prequisite for Ord)
	//+ equals :: Coord ~> Coord -> Boolean
	Coord.prototype.equals = function coordEquals(that) {
	return this.x == that.x
	&& this.y == that.y
	&& this.z == that.z
	}

	//- Ord instance for Coord
	//+ lte :: Coord ~> Coord -> Boolean
	Coord.prototype.lte = function coordLte(that) {
	return (this.x < that.x)
	\|\| (this.x == that.x && this.y < that.y)
	\|\| (this.x == that.x && this.y == that.y && this.z < that.z)
	\|\| (this.equals(that))
	}

	//- A line between two coordinates
	//+ Line :: (Coord, Coord) -> Line
	const Line = daggy.tagged('Coord', ['from', 'to'])

	//- Setoid instance for Line (prequisite for Ord)
	//+ equals :: Line ~> Line -> Boolean
	Line.prototype.equals = function lineEquals(that) {
	return this.from.equals(that.from)
	&& this.to.equals(that.to)
	}

	//- Ord instance of Line
	//+ lte :: Line ~> Line -> Boolean
	Line.prototype.lte = function lineLte(that) {
	return (lt(this.from, that.from))
	\|\| (this.from.equals(that.from) && lt(this.to, that.to))
	\|\| (this.equals(that))
	}

	// Derived Ord operations
	// With `lte` and `equals` we can derive all the other Ord operations we want

	// lte :: Ord a => a -> a -> Boolean
	const lte = function ordLte(x, y) {
	return x.lte(y)
	}

	// Greater than. The OPPOSITE of lte.
	// gt :: Ord a => a -> a -> Boolean
	const gt = function ordGt(x, y) {
	return !lte(x, y)
	}

	// Greater than OR equals
	// gte :: Ord a => a -> a -> Boolean
	const gte = function ordGte(x, y) {
	return gt(x, y) \|\| x.equals(y)
	}

	// Less than. The OPPOSITE of gte
	// lt :: Ord a => a -> a -> Boolean
	const lt = function ordLt(x, y) {
	return !gte(x, y)
	}

	/*
	* Sorts
	* - Each make copies rather than modifying list in place
	*/
	const copy = xs => [...xs]

	//- Sort a list of Ords using bubble sort algorithm
	// bubbleSort :: Ord a => [a] -> [a]
	const bubbleSort = xs_ => {
	const xs = copy(xs_)
	let n = xs.length - 1
	let swapped = true
	while (swapped) {
	swapped = false
	for (let i = 1; i <= n; i++) {
	const curr = xs[i]
	const prev = xs[i - 1]
	if (gt(prev, curr)) {
	xs[i - 1] = curr
	xs[i] = prev
	swapped = true
	}
	}
	}
	return xs
	}

	//- Sort a list of Ords using merge sort algorithm
	//+ mergeSort :: Ord a => [a] -> [a]
	const mergeSort = m => {
	if (m.length <= 1) return m

	const left = []
	const right = []
	m.forEach((x, i) => {
	if (i < (m.length / 2)) {
	left.push(x)
	} else {
	right.push(x)
	}
	})

	const leftSorted = mergeSort(left)
	const rightSorted = mergeSort(right)

	return _merge(leftSorted, rightSorted)
	}

	const _merge = (left, right) => {
	const result = []
	let l = copy(left)
	let r = copy(right)

	while (l.length > 0 && r.length > 0) {
	const [lhead, ...ltail] = l
	const [rhead, ...rtail] = r

	if (lte(lhead, rhead)) {
	result.push(lhead)
	l = ltail
	} else {
	result.push(rhead)
	r = rtail
	}
	}

	// Either left or right may have elements left; consume them
	// (Only one of the following loops will actually be entered)
	if (l.length > 0) {
	result.push(...l)
	}
	if (r.length > 0) {
	result.push(...r)
	}

	return result
	}

	//- Sort a list of Ords using quicksort algorithm
	//+ quickSort :: Ord a => [a] -> [a]
	const quickSort = xs => _quickSort(copy(xs), 0, xs.length - 1)

	const _quickSort = (xs, lo, hi) => {
	if (lo < hi) {
	const p = _partition(xs, lo, hi)
	_quickSort(xs, lo, p - 1)
	_quickSort(xs, p + 1, hi)
	}
	return xs
	}

	const _partition = (xs, lo, hi) => {
	const pivot = xs[hi]
	let i = lo
	for (let j = lo; j < hi; j++) {
	if (lt(xs[j], pivot)) {
	if (i != j) {
	const xsi = xs[i]
	const xsj = xs[j]
	xs[i] = xsj
	xs[j] = xsi
	}
	i++
	}
	}
	const xsi = xs[i]
	const xshi = xs[hi]
	xs[i] = xshi
	xs[hi] = xsi
	return i
	}


	/*
	* Demonstrations
	*/

	const coord_list = [
	Coord(1, 2, 3),
	Coord(1, 2, 1),
	Coord(1, 1, 2)
	]

	const line_list = [
	Line (
	origin,
	Coord(1, 2, 3)
	),
	Line (
	Coord(1, 2, 1),
	Coord(1, 2, 2),
	),
	Line(
	origin,
	Coord(1, 1, 2)
	)
	]

	// bubbleSort(coord_list)
	// mergeSort(coord_list)
	// quickSort(coord_list)
	// -> [
	// { x: 1, y: 1, z: 2 },
	// { x: 1, y: 2, z: 1 },
	// { x: 1, y: 2, z: 3 }
	// ]

	// bubbleSort(line_list)
	// mergeSort(line_list)
	// quickSort(line_list)
	// -> [
	// { from: { x: 0, y: 0, z: 0 }, to: { x: 1, y: 1, z: 2 } },
	// { from: { x: 0, y: 0, z: 0 }, to: { x: 1, y: 2, z: 3 } },
	// { from: { x: 1, y: 2, z: 1 }, to: { x: 1, y: 2, z: 2 } }
	// ]