5406352152

import { Value } from '../types'
import { ArrayLike, stringify } from '../utils/stringify'

// list.ts: Supporting lists in the Scheme style, using pairs made
//          up of two-element JavaScript array (vector)
// Author: Martin Henz
// Translated to TypeScript by Evan Sebastian
export type Pair<H, T> = [H, T]
export type List = null | NonEmptyList
type NonEmptyList = Pair<any, any>

// array test works differently for Rhino and
// the Firefox environment (especially Web Console)
function array_test(x: any) {
  if (Array.isArray === undefined) {
    return x instanceof Array
  } else {
    return Array.isArray(x)
  }
}

// pair constructs a pair using a two-element array
// LOW-LEVEL FUNCTION, NOT SOURCE
export function pair<H, T>(x: H, xs: T): Pair<H, T> {
  return [x, xs]
}

// is_pair returns true iff arg is a two-element array
// LOW-LEVEL FUNCTION, NOT SOURCE
export function is_pair(x: any) {
  return array_test(x) && x.length === 2
}

// head returns the first component of the given pair,
// throws an exception if the argument is not a pair
// LOW-LEVEL FUNCTION, NOT SOURCE
export function head(xs: any) {
  if (is_pair(xs)) {
    return xs[0]
  } else {
    throw new Error('head(xs) expects a pair as argument xs, but encountered ' + stringify(xs))
  }
}

// tail returns the second component of the given pair
// throws an exception if the argument is not a pair
// LOW-LEVEL FUNCTION, NOT SOURCE
export function tail(xs: any) {
  if (is_pair(xs)) {
    return xs[1]
  } else {
    throw new Error('tail(xs) expects a pair as argument xs, but encountered ' + stringify(xs))
  }
}

// is_null returns true if arg is exactly null
// LOW-LEVEL FUNCTION, NOT SOURCE
export function is_null(xs: List) {
  return xs === null
}

// list makes a list out of its arguments
// LOW-LEVEL FUNCTION, NOT SOURCE
export function list(...elements: any[]): List {
  let theList = null
  for (let i = elements.length - 1; i >= 0; i -= 1) {
    theList = pair(elements[i], theList)
  }
  return theList
}

// recurses down the list and checks that it ends with the empty list null
// LOW-LEVEL FUNCTION, NOT SOURCE
export function is_list(xs: List) {
  while (is_pair(xs)) {
    xs = tail(xs)
  }
  return is_null(xs)
}

// list_to_vector returns vector that contains the elements of the argument list
// in the given order.
// list_to_vector throws an exception if the argument is not a list
// LOW-LEVEL FUNCTION, NOT SOURCE
export function list_to_vector(lst: List) {
  const vector = []
  while (!is_null(lst)) {
    vector.push(head(lst))
    lst = tail(lst)
  }
  return vector
}

// vector_to_list returns a list that contains the elements of the argument vector
// in the given order.
// vector_to_list throws an exception if the argument is not a vector
// LOW-LEVEL FUNCTION, NOT SOURCE
export function vector_to_list(vector: any[]): List {
  return list(...vector)
}

// set_head(xs,x) changes the head of given pair xs to be x,
// throws an exception if the argument is not a pair
// LOW-LEVEL FUNCTION, NOT SOURCE

export function set_head(xs: any, x: any) {
  if (is_pair(xs)) {
    xs[0] = x
    return undefined
  } else {
    throw new Error(
      'set_head(xs,x) expects a pair as argument xs, but encountered ' + stringify(xs)
    )
  }
}

// set_tail(xs,x) changes the tail of given pair xs to be x,
// throws an exception if the argument is not a pair
// LOW-LEVEL FUNCTION, NOT SOURCE

export function set_tail(xs: any, x: any) {
  if (is_pair(xs)) {
    xs[1] = x
    return undefined
  } else {
    throw new Error(
      'set_tail(xs,x) expects a pair as argument xs, but encountered ' + stringify(xs)
    )
  }
}

/**
 * Accumulate applies given operation op to elements of a list
 * in a right-to-left order, first apply op to the last element
 * and an initial element, resulting in r1, then to the second-last
 * element and r1, resulting in r2, etc, and finally to the first element
 * and r_n-1, where n is the length of the list. `accumulate(op,zero,list(1,2,3))`
 * results in `op(1, op(2, op(3, zero)))`
 */
export function accumulate<T, U>(op: (each: T, result: U) => U, initial: U, sequence: List): U {
  // Use CPS to prevent stack overflow
  function $accumulate(xs: typeof sequence, cont: (each: U) => U): U {
    return is_null(xs) ? cont(initial) : $accumulate(tail(xs), x => cont(op(head(xs), x)))
  }
  return $accumulate(sequence, x => x)
}

export function length(xs: List): number {
  if (!is_list(xs)) {
    throw new Error('length(xs) expects a list')
  }

  return accumulate((_, total) => total + 1, 0, xs)
}

export function rawDisplayList(display: any, xs: Value, prepend: string) {
  const visited: Set<Value> = new Set() // Everything is put into this set, values, arrays, and even objects if they exist
  const asListObjects: Map<NonEmptyList, NonEmptyList | ListObject> = new Map() // maps original list nodes to new list nodes

  // We will convert list-like structures in xs to ListObject.
  class ListObject implements ArrayLike {
    replPrefix = 'list('
    replSuffix = ')'
    replArrayContents(): Value[] {
      const result: Value[] = []
      let curXs = this.listNode
      while (curXs !== null) {
        result.push(head(curXs))
        curXs = tail(curXs)
      }
      return result
    }
    listNode: List

    constructor(listNode: List) {
      this.listNode = listNode
    }
  }
  function getListObject(curXs: Value): Value {
    return asListObjects.get(curXs) || curXs
  }

  const pairsToProcess: Value[] = []
  let i = 0
  pairsToProcess.push(xs)
  // we need the guarantee that if there are any proper lists,
  // then the nodes of the proper list appear as a subsequence of this array.
  // We ensure this by always adding the tail after the current node is processed.
  // This means that sometimes, we add the same pair more than once!
  // But because we only process each pair once due to the visited check,
  // and each pair can only contribute to at most 3 items in this array,
  // this array has O(n) elements.
  while (i < pairsToProcess.length) {
    const curXs = pairsToProcess[i]
    i++
    if (visited.has(curXs)) {
      continue
    }
    visited.add(curXs)
    if (!is_pair(curXs)) {
      continue
    }
    pairsToProcess.push(head(curXs), tail(curXs))
  }

  // go through pairs in reverse to ensure the dependencies are resolved first
  while (pairsToProcess.length > 0) {
    const curXs = pairsToProcess.pop()
    if (!is_pair(curXs)) {
      continue
    }
    const h = head(curXs)
    const t = tail(curXs)
    const newTail = getListObject(t) // the reason why we need the above guarantee
    const newXs =
      is_null(newTail) || newTail instanceof ListObject
        ? new ListObject(pair(h, t)) // tail is a proper list
        : pair(h, t) // it's not a proper list, make a copy of the pair so we can change references below
    asListObjects.set(curXs, newXs)
  }

  for (const curXs of asListObjects.values()) {
    if (is_pair(curXs)) {
      set_head(curXs, getListObject(head(curXs)))
      set_tail(curXs, getListObject(tail(curXs)))
    } else if (curXs instanceof ListObject) {
      set_head(curXs.listNode, getListObject(head(curXs.listNode)))
      let newTail = getListObject(tail(curXs.listNode))
      if (newTail instanceof ListObject) {
        newTail = newTail.listNode
      }
      set_tail(curXs.listNode, newTail)
    }
  }
  display(getListObject(xs), prepend)
  return xs
}

1	import { Value } from '../types'
2	import { ArrayLike, stringify } from '../utils/stringify'	67✔
3
4	// list.ts: Supporting lists in the Scheme style, using pairs made
5	// up of two-element JavaScript array (vector)
6	// Author: Martin Henz
7	// Translated to TypeScript by Evan Sebastian
8	export type Pair<H, T> = [H, T]
9	export type List = null \| NonEmptyList
10	type NonEmptyList = Pair<any, any>
11
12	// array test works differently for Rhino and
13	// the Firefox environment (especially Web Console)
14	function array_test(x: any) {
15	if (Array.isArray === undefined) {	68,505!
16	return x instanceof Array	×
17	} else {
18	return Array.isArray(x)	68,505✔
19	}
20	}
21
22	// pair constructs a pair using a two-element array
23	// LOW-LEVEL FUNCTION, NOT SOURCE
24	export function pair<H, T>(x: H, xs: T): Pair<H, T> {	67✔
25	return [x, xs]	26,886✔
26	}
27
28	// is_pair returns true iff arg is a two-element array
29	// LOW-LEVEL FUNCTION, NOT SOURCE
30	export function is_pair(x: any) {	67✔
31	return array_test(x) && x.length === 2	68,505✔
32	}
33
34	// head returns the first component of the given pair,
35	// throws an exception if the argument is not a pair
36	// LOW-LEVEL FUNCTION, NOT SOURCE
37	export function head(xs: any) {	67✔
38	if (is_pair(xs)) {	25,280✔
39	return xs[0]	25,257✔
40	} else {
41	throw new Error('head(xs) expects a pair as argument xs, but encountered ' + stringify(xs))	23✔
42	}
43	}
44
45	// tail returns the second component of the given pair
46	// throws an exception if the argument is not a pair
47	// LOW-LEVEL FUNCTION, NOT SOURCE
48	export function tail(xs: any) {	67✔
49	if (is_pair(xs)) {	33,202✔
50	return xs[1]	33,176✔
51	} else {
52	throw new Error('tail(xs) expects a pair as argument xs, but encountered ' + stringify(xs))	26✔
53	}
54	}
55
56	// is_null returns true if arg is exactly null
57	// LOW-LEVEL FUNCTION, NOT SOURCE
58	export function is_null(xs: List) {	67✔
59	return xs === null	38,308✔
60	}
61
62	// list makes a list out of its arguments
63	// LOW-LEVEL FUNCTION, NOT SOURCE
64	export function list(...elements: any[]): List {	67✔
65	let theList = null	4,970✔
66	for (let i = elements.length - 1; i >= 0; i -= 1) {	4,970✔
67	theList = pair(elements[i], theList)	20,223✔
68	}
69	return theList	4,970✔
70	}
71
72	// recurses down the list and checks that it ends with the empty list null
73	// LOW-LEVEL FUNCTION, NOT SOURCE
74	export function is_list(xs: List) {	67✔
75	while (is_pair(xs)) {	11✔
76	xs = tail(xs)	13✔
77	}
78	return is_null(xs)	11✔
79	}
80
81	// list_to_vector returns vector that contains the elements of the argument list
82	// in the given order.
83	// list_to_vector throws an exception if the argument is not a list
84	// LOW-LEVEL FUNCTION, NOT SOURCE
85	export function list_to_vector(lst: List) {	67✔
86	const vector = []	2✔
87	while (!is_null(lst)) {	2✔
88	vector.push(head(lst))	6✔
89	lst = tail(lst)	6✔
90	}
91	return vector	2✔
92	}
93
94	// vector_to_list returns a list that contains the elements of the argument vector
95	// in the given order.
96	// vector_to_list throws an exception if the argument is not a vector
97	// LOW-LEVEL FUNCTION, NOT SOURCE
98	export function vector_to_list(vector: any[]): List {	67✔
99	return list(...vector)	1,470✔
100	}
101
102	// set_head(xs,x) changes the head of given pair xs to be x,
103	// throws an exception if the argument is not a pair
104	// LOW-LEVEL FUNCTION, NOT SOURCE
105
106	export function set_head(xs: any, x: any) {	67✔
107	if (is_pair(xs)) {	903✔
108	xs[0] = x	901✔
109	return undefined	901✔
110	} else {
111	throw new Error(	2✔
112	'set_head(xs,x) expects a pair as argument xs, but encountered ' + stringify(xs)
113	)
114	}
115	}
116
117	// set_tail(xs,x) changes the tail of given pair xs to be x,
118	// throws an exception if the argument is not a pair
119	// LOW-LEVEL FUNCTION, NOT SOURCE
120
121	export function set_tail(xs: any, x: any) {	67✔
122	if (is_pair(xs)) {	942✔
123	xs[1] = x	940✔
124	return undefined	940✔
125	} else {
126	throw new Error(	2✔
127	'set_tail(xs,x) expects a pair as argument xs, but encountered ' + stringify(xs)
128	)
129	}
130	}
131
132	/**
133	* Accumulate applies given operation op to elements of a list
134	* in a right-to-left order, first apply op to the last element
135	* and an initial element, resulting in r1, then to the second-last
136	* element and r1, resulting in r2, etc, and finally to the first element
137	* and r_n-1, where n is the length of the list. `accumulate(op,zero,list(1,2,3))`
138	* results in `op(1, op(2, op(3, zero)))`
139	*/
140	export function accumulate<T, U>(op: (each: T, result: U) => U, initial: U, sequence: List): U {	67✔
141	// Use CPS to prevent stack overflow
142	function $accumulate(xs: typeof sequence, cont: (each: U) => U): U {
143	return is_null(xs) ? cont(initial) : $accumulate(tail(xs), x => cont(op(head(xs), x)))	×
144	}
145	return $accumulate(sequence, x => x)	×
146	}
147
148	export function length(xs: List): number {	67✔
149	if (!is_list(xs)) {	×
150	throw new Error('length(xs) expects a list')	×
151	}
152
153	return accumulate((_, total) => total + 1, 0, xs)	×
154	}
155
156	export function rawDisplayList(display: any, xs: Value, prepend: string) {	67✔
157	const visited: Set<Value> = new Set() // Everything is put into this set, values, arrays, and even objects if they exist	36✔
158	const asListObjects: Map<NonEmptyList, NonEmptyList \| ListObject> = new Map() // maps original list nodes to new list nodes	36✔
159
160	// We will convert list-like structures in xs to ListObject.
161	class ListObject implements ArrayLike {
162	replPrefix = 'list('	775✔
163	replSuffix = ')'	775✔
164	replArrayContents(): Value[] {
165	const result: Value[] = []	168✔
166	let curXs = this.listNode	168✔
167	while (curXs !== null) {	168✔
168	result.push(head(curXs))	775✔
169	curXs = tail(curXs)	775✔
170	}
171	return result	168✔
172	}
173	listNode: List
174
175	constructor(listNode: List) {
176	this.listNode = listNode	775✔
177	}
178	}
179	function getListObject(curXs: Value): Value {
180	return asListObjects.get(curXs) \|\| curXs	2,775✔
181	}
182
183	const pairsToProcess: Value[] = []	36✔
184	let i = 0	36✔
185	pairsToProcess.push(xs)	36✔
186	// we need the guarantee that if there are any proper lists,
187	// then the nodes of the proper list appear as a subsequence of this array.
188	// We ensure this by always adding the tail after the current node is processed.
189	// This means that sometimes, we add the same pair more than once!
190	// But because we only process each pair once due to the visited check,
191	// and each pair can only contribute to at most 3 items in this array,
192	// this array has O(n) elements.
193	while (i < pairsToProcess.length) {	36✔
194	const curXs = pairsToProcess[i]	1,834✔
195	i++	1,834✔
196	if (visited.has(curXs)) {	1,834✔
197	continue	710✔
198	}
199	visited.add(curXs)	1,124✔
200	if (!is_pair(curXs)) {	1,124✔
201	continue	225✔
202	}
203	pairsToProcess.push(head(curXs), tail(curXs))	899✔
204	}
205
206	// go through pairs in reverse to ensure the dependencies are resolved first
207	while (pairsToProcess.length > 0) {	36✔
208	const curXs = pairsToProcess.pop()	1,834✔
209	if (!is_pair(curXs)) {	1,834✔
210	continue	893✔
211	}
212	const h = head(curXs)	941✔
213	const t = tail(curXs)	941✔
214	const newTail = getListObject(t) // the reason why we need the above guarantee	941✔
215	const newXs =
216	is_null(newTail) \|\| newTail instanceof ListObject	941✔
217	? new ListObject(pair(h, t)) // tail is a proper list	941✔
218	: pair(h, t) // it's not a proper list, make a copy of the pair so we can change references below
219	asListObjects.set(curXs, newXs)	941✔
220	}
221
222	for (const curXs of asListObjects.values()) {	36✔
223	if (is_pair(curXs)) {	899✔
224	set_head(curXs, getListObject(head(curXs)))	130✔
225	set_tail(curXs, getListObject(tail(curXs)))	130✔
226	} else if (curXs instanceof ListObject) {	769✔
227	set_head(curXs.listNode, getListObject(head(curXs.listNode)))	769✔
228	let newTail = getListObject(tail(curXs.listNode))	769✔
229	if (newTail instanceof ListObject) {	769✔
230	newTail = newTail.listNode	607✔
231	}
232	set_tail(curXs.listNode, newTail)	769✔
233	}
234	}
235	display(getListObject(xs), prepend)	36✔
236	return xs	36✔
237	}

source-academy / js-slang / 5406352152

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous