Re:Löb and möb: strange loops in Haskell
by love2read on Monday January 30, 2023 @01:27PM
(#34584165)
How hard would it be to describe this in terms of javascript?
[ Parent
| on HN ]
Re:Löb and möb: strange loops in Haskell
by lalaithion on Monday January 30, 2023 @02:52PM
(#34585454)
Pretty hard. The key to this implementation is Haskell's laziness, so you have to implement laziness in Javascript, which will probably not be very ergonomic. You can write
let loeb = (structure => {
let inner = () => structure.map(item => item(inner()));
return inner;
})
let fs = [ _ => 1
, x => x[0] + 1
, x => x[1] + 1
, x => x[2] + 1
]
console.log(loeb(fs)())
and get an infinite loop, or let loeb = (structure => {
let inner = () => structure.map(item => item(inner));
return inner;
})
let fs = [ _ => 1
, x => x[0] + 1
, x => x[1] + 1
, x => x[2] + 1
]
console.log(loeb(fs)())
and get [1, null, null, null].
Re:Löb and möb: strange loops in Haskell
by contravariant on Monday January 30, 2023 @05:32PM
(#34587476)
You can typically simulate laziness by lifting variables into functions. A 0-arity function works fine, but for lists it's slightly more elegant to define them as functions from an index to a value (in that case the functor map is just composition, which is neat).
So the following works
let loeb = (structure => {
let inner = (i) => structure(i)(inner);
return inner;
})
let fs = (i) => {switch(i) {
case 0: return _ => 1
case 1: return (x) => x(0) + 1
case 2: return (x) => x(1) + 1
case 3: return (x) => x(2) + 1
}}
If javascript was sensible you could just do let fs = [ _ => 1
, x => x(0) + 1
, x => x(1) + 1
, x => x(2) + 1
].at
but alas that doesn't work, you can do let fs = (i) => [ _ => 1
, x => x(0) + 1
, x => x(1) + 1
, x => x(2) + 1
][i]
though. In that case javascript may end up rebuilding the list every time, I'm not quite sure.
Re:Löb and möb: strange loops in Haskell
by gowld on Thursday February 02, 2023 @11:42AM
(#34629064)
Python:
def done(x):
return (type(x) != type(lambda: None))
def allof(f, *xs):
return all(map(f, xs))
def isnt(f):
return lambda x: not f(x)
def myprint(xs):
print("\t-> ", "\t".join([str(x) if done(x) else "_" for x in xs]))
def lazy(f, *deps):
"Evaluate f(xs), only if dependencies (listed by index in xs) are resolved."
def lazy_f(xs):
if allof(done, *[xs[d] for d in deps]):
return f(xs)
else:
return lazy(f, *deps)
return lazy_f
def loeb_unsafe(fs):
"Loeb for lists, but doesn't detect dependency cycles."
xs = fs[:]
# THE IMPORTANT PART!
while not allof(done, *xs):
# 'if done(x) is special for Python: convert function to value, since
# Python doesn't know how to evaluate/call a value like Haskell does.
xs = [x if done(x) else x(xs) for x in xs]
return xs
def loeb_safe(fs):
"Loeb for lists, stops when it detects a dependency cycle."
xs = fs[:]
# THE IMPORTANT PART!
while not allof(done, *xs):
myprint(xs)
# 'if done(x) is special for Python: convert function to value, since
# Python doesn't know how to evaluate/call a value like Haskell does.
new_xs = [x if done(x) else x(xs) for x in xs]
if list(filter(done, new_xs)) == list(filter(done, xs)):
print("CYCLE DETECTED!")
break
xs = new_xs
return xs
fs = [
lazy(lambda xs: xs[1] + xs[2], 1, 2),
lazy(lambda xs: xs[3] + 1, 3),
lazy(lambda xs: xs[1] + 1, 1),
1,
lazy(lambda xs: xs[5] + 1, 5),
# unsafe!
# lazy(lambda xs: xs[4] + 1, 4),
lambda xs: 100,
200
]
print("safe:")
myprint(loeb_safe(fs))
print("\nunsafe:")
myprint(loeb_unsafe(fs))
Output: safe:
-> _ _ _ 1 _ _ 200
-> _ 2 _ 1 _ 100 200
-> _ 2 3 1 101 100 200
-> 5 2 3 1 101 100 200
unsafe:
-> 5 2 3 1 101 100 200