Естественно писать RevExp.toString как рекурсивную программу, потому что ожидается, что она будет обрабатывать рекурсивно структурированный ввод. Однако, поскольку рекурсивные программы могут приводить к глубоким стекам, нередко сводят рекурсивный процесс к итеративному.
Хорошие программисты знают, что поддержание сложности имеет большое значение для поддержания нашего рассудка. Я хочу сохранить свою рекурсивную программу, и я хочу, чтобы компьютер обрабатывал этот процесс за меня. Можно мне пирог и тоже его съесть?
Вот еще один способ решить проблему -
// example1.js
import { concat, upper, digit, str, toString } from './RevExp.js'
const licensePlate =
concat(upper(), upper(), upper(), str("-"), digit(), digit(), digit())
console.log(toString(licensePlate))
console.log(toString(licensePlate))
console.log(toString(licensePlate))
// RFX-559
// VKT-794
// KSF-823
Приступим к написанию модуля RevExp. Мы начнем с создания конструкторов для каждого из наших типов выражений -
// RevExp.js
const str = (value = "") =>
({ type: str, value })
const lower = () =>
({ type: lower })
const upper = () =>
({ type: upper })
const digit = ({ zero = true } = {}) =>
({ type: digit, zero })
const concat = (...exprs) =>
({ type: concat, exprs })
Теперь поработаем над RevExp.toString -
// RevExp.js (continued)
import { inRange } from './Rand.js'
const toString = (e) =>
{ switch (e.type)
{ case str:
return String(e.value)
case lower:
return String.fromCharCode(inRange(97, 122))
case upper:
return String.fromCharCode(inRange(65, 90))
case digit:
return e.zero
? String(inRange(0, 9))
: String(inRange(1, 9))
case concat:
return e.exprs.reduce((r, v) => r + toString(v), "")
default: throw Error(`unsupported expression type: ${e.type}`)
}
}
export { lower, upper, digit, alpha, repeat, concat, str, toString }
Должна быть возможность составлять сложные выражения, комбинируя несколько простых выражений. И мы представляем себе некоторые новые типы, такие как alpha и repeat -
// example2.js
import { alpha, digit, repeat, concat, str, toString } from './RevExp.js'
const segment =
concat(alpha(), digit(), alpha(), digit(), alpha())
const serial =
concat
( repeat
( concat(segment, str("-"))
, { count: 4 }
)
, segment
)
console.log(toString(serial))
console.log(toString(serial))
console.log(toString(serial))
// F3Q7U-b6k8Q-R8e3A-a2q3M-j0a9k
// g6G3w-h2O3O-b8O3k-L4p1y-m5I0y
// m6E0M-A4C2y-K3g0M-d7X7j-w8v5G
И добавить соответствующую поддержку в модуле RevExp -
// RevExp.js (enhanced)
import { inRange, sample } from './Rand.js'
const str = // ...
const lower = // ...
const upper = // ...
const digit = // ...
const concat = // ...
const alpha = () =>
oneOf(upper(), lower())
const oneOf = (...exprs) =>
({ type: oneOf, exprs })
const repeat = (expr = {}, { count = 10 } = {}) =>
({ type: repeat, expr, count })
const toString = (e) =>
{ switch (e.type)
{ case str: // ...
case lower: // ...
case upper: // ...
case digit: // ...
case concat: // ...
case oneOf:
return toString(sample(e.exprs))
case repeat:
return toString(concat(...Array(e.count).fill(e.expr)))
default: // ...
}
}
export { /* ..., */ alpha, oneOf, repeat }
Теперь преобразуем рекурсивную программу в итеративную. И без необходимости думать о стеке или изменении состояния во время работы программы!
// RevExp.js (stack-safe)
// ...
import * as Str from './Str.js'
import { loop, recur, call } from './TailRec.js'
// ...
const toString = (e = {}) =>
loop(toStringTailRec, e)
const toStringTailRec = e =>
{ switch (e.type)
{ case str: // ...
case lower: // ...
case upper: // ...
case digit: // ...
case concat:
return e.exprs.length
? call
( Str.concat
, recur(e.exprs[0])
, recur(concat(...e.exprs.slice(1)))
)
: Str.empty
case oneOf:
return recur(sample(e.exprs))
case repeat:
return recur(concat(...Array(e.count).fill(e.expr)))
default: throw Error(`unsupported expression type: ${e.type}`)
}
}
export { /*...*/, toString } // <-- don't export toStringTailRec helper
А вот оставшиеся модули Str, Rand и TailRec -
// Str.js
const empty =
""
const concat = (a = "", b = "") =>
a + b
export { empty, concat }
// Rand.js
const rand = (n = 2) =>
Math.floor(Math.random() * n)
const inRange = (min = 0, max = 1) =>
rand(max - min + 1) + min
const sample = (t = []) =>
t[rand(t.length)]
export { rand, inRange, sample }
Написание модулей - важный фактор в создании повторно используемого кода. Этот TailRec модуль был написан в другом сообщении и может быть повторно использован без изменений 1 , чтобы удовлетворить потребности нашей программы.
Теперь мы можем полагаться на рекурсивно структурированные программы, не добавляя сложности и не требуя изменения своего мышления каждый раз, когда мы сталкиваемся с рекурсивной проблемой. Запишите модуль один раз, используйте повторно по мере необходимости -
// TailRec.js
const identity = x =>
x
const call = (f, ...values) =>
({ type: call, f, values })
const recur = (...values) =>
({ type: recur, values })
const loop = (f, ...init) =>
{ const aux1 = (e, k) =>
e.type === recur
? call(aux, e.values, r => call(aux1, f(...r), k))
: e.type === call
? call(aux, e.values, r => call(aux1, e.f(...r), k))
: call(k, e)
const aux = (exprs, k) =>
call
( exprs.reduce
( (mr, e) =>
k => call(mr, r => call(aux1, e, x => call(k, [ ...r, x ])))
, k => call(k, [])
)
, k
)
return run(aux1(f(...init), identity))
}
const run = r =>
{ while (r && r.type === call)
r = r.f(...r.values)
return r
}
export { loop, call, recur }
В конце концов, здесь подход практически такой же, как и у вас. Однако вместо представления выражений, записывающих объекты JS вручную, мы используем функции, которые можно параметризовать и составить, и которые могут обрабатывать утомительную и ненадежную сборку за нас. Вменяемость программиста сохраняется -
// example2.js
// ...
console.log(serial)
{ type: concat
, exprs:
[ { type: repeat
, expr:
{ type: concat
, exprs:
[ { type: concat
, exprs:
[ { type: oneOf, exprs: [ { type: lower }, { type: upper } ] }
, { type: digit, zero: true }
, { type: oneOf, exprs: [ { type: lower }, { type: upper } ] }
, { type: digit, zero: true }
, { type: oneOf, exprs: [ { type: lower }, { type: upper } ] }
]
}
, { type: str, value: "-" }
]
}
, count: 4
}
, { type: concat
, exprs:
[ { type: concat
, exprs:
[ { type: oneOf, exprs: [ { type: lower }, { type: upper } ] }
, { type: digit, zero: true }
, { type: oneOf, exprs: [ { type: lower }, { type: upper } ] }
, { type: digit, zero: true }
, { type: oneOf, exprs: [ { type: lower }, { type: upper } ] }
]
}
]
}
]
}
Я надеюсь, что это было замечено как захватывающий способ взглянуть на ту же проблему с другой точки зрения. Если вы в конечном итоге используете модуль TailRec, см. Дополнительные объяснения в исходной публикации. Я буду рад ответить на любые дополнительные вопросы.
1. Незначительные изменения форматирования и переименование переменных для согласованности с этим ответом.
person
Mulan
schedule
06.08.2020
