How do I define y-combinator without let rec?
As the compiler points out, there is no type that can be assigned to x so that the expression (x x) is well-typed (this isn't strictly true; you can explicitly type x as obj->_ - see my last paragraph). You can work around this issue by declaring a recursive type so that a very similar expression will work:
type 'a Rec = Rec of ('a Rec -> 'a)
Now the Y-combinator can be written as:
let y f =
let f' (Rec x as rx) = f (x rx)
f' (Rec f')
Unfortunately, you'll find that this isn't very useful because F# is a strict language,
so any function that you try to define using this combinator will cause a stack overflow.
Instead, you need to use the applicative-order version of the Y-combinator (\f.(\x.f(\y.(x x)y))(\x.f(\y.(x x)y))):
let y f =
let f' (Rec x as rx) = f (fun y -> x rx y)
f' (Rec f')
Another option would be to use explicit laziness to define the normal-order Y-combinator:
type 'a Rec = Rec of ('a Rec -> 'a Lazy)
let y f =
let f' (Rec x as rx) = lazy f (x rx)
(f' (Rec f')).Value
This has the disadvantage that recursive function definitions now need an explicit force of the lazy value (using the Value property):
let factorial = y (fun f -> function | 0 -> 1 | n -> n * (f.Value (n - 1)))
However, it has the advantage that you can define non-function recursive values, just as you could in a lazy language:
let ones = y (fun ones -> LazyList.consf 1 (fun () -> ones.Value))
As a final alternative, you can try to better approximate the untyped lambda calculus by using boxing and downcasting. This would give you (again using the applicative-order version of the Y-combinator):
let y f =
let f' (x:obj -> _) = f (fun y -> x x y)
f' (fun x -> f' (x :?> _))
This has the obvious disadvantage that it will cause unneeded boxing and unboxing, but at least this is entirely internal to the implementation and will never actually lead to failure at runtime.
Issue passing a closure that takes an escaping closure to a function that accepts a closure of that type
Your Y function should have the following signature:
func Y<T, R>(_ f: @escaping (@escaping (T) -> R) -> ((T) -> R)) -> ((T) -> R)
since it accepts an escaping function which itself needs an escaping function.
When you call Y, the closure should start with:
self.Y { (f: @escaping () -> ()) -> (() -> ()) in
notice that this @escaping corresponds to the second escaping in the Y signature. It was a mismatch on this @escaping that was causing your compiler error.
Most of the rest should sort itself out (once you update the Dispatch and NSNotificationCenter calls to Swift 3).
What is a Y-combinator?
If you're ready for a long read, Mike Vanier has a great explanation. Long story short, it allows you to implement recursion in a language that doesn't necessarily support it natively.
Swift 4 JSON Decodable from Hacker News API not in correct order?
You are doing async calls to fetch the articles. There is no guarantee as to what order those will complete. They may tend to complete in order, or maybe not. You should not assume that they will.
You need a data structure that preserves your order. You could save an array of article IDs, and then create a dictionary where the key is the article ID and the value is the content of the article.
To populate your table view you'd look up the article ID in the array of article IDs at the specified row, then use that article ID to fetch the article from your dictionary of articles.
Calling reloadData on the table view for every article is a bad idea performance-wise. You should instead look for the article ID in your array of article IDs, then tell the view controller that manages the table view to update that index. In the view controller, use reloadRows(at:with:) to tell the table view to reload the cells who's data has just been reloaded. That will prevent you from re-rendering the whole table view for each cell.
EDIT:
As mentioned in my comment, your code to decode the array is a mess. It's JSON data, so you could either use the older JSONSerialization style, or the new JSONDecoder class added in Swift 4. That code would look like this:
let jsonString = """
[16249058,16248449,16249048,16246805,16232898,16248247,16245216,16247254,16248747,16246432,16245817,16247964,16238367,16220646,16248660,16248782,16246485,16243067,16245773,16245873,16247109,16248704,16248860,16235983,16237655,16246093,16247577,16245108,16242380,16246807,16220298,16242908,16246531,16247165,16246691,16246690,16243306,16247667,16246297,16245606,16221166,16246817,16247921,16247847,16247093,16245697,16247958,16242336,16248889,16248587,16248866,16244298,16246544,16240587,16238937,16248810,16248079,16240234,16244835,16245284,16246424,16236832,16246906,16240911,16243784,16243795,16244564,16244175,16241454,16243539,16248336,16243506,16230933,16246227,16243207,16244580,16243276,16239822,16240644,16245142,16246929,16247474,16242506,16235044,16244827,16245034,16241007,16244194,16243127,16238806,16246203,16243700,16246003,16239446,16242955,16244668,16218439,16240874,16242383,16237558,16225455,16234213,16242060,16230464,16245665,16245586,16234060,16241659,16242037,16232480,16240345,16239839,16235634,16245229,16237854,16237462,16240656,16247776,16242624,16224427,16237609,16235899,16241024,16241294,16222478,16233644,16243223,16241524,16232946,16242293,16247409,16238501,16241226,16235417,16246021,16244010,16245807,16239389,16221661,16246497,16228138,16227009,16245725,16227636,16240183,16240871,16246615,16233859,16233325,16238465,16237227,16233953,16239843,16245932,16220017,16230541,16237509,16241570,16242826,16222520,16246890,16241208,16226923,16232509,16233578,16245077,16236104,16242925,16216960,16222342,16245736,16225531,16218872,16238535,16239594,16234067,16227139,16235062,16238796,16236397,16237026,16240485,16239992,16238322,16237437,16236692,16242855,16219251,16240772,16225386,16223929,16237920,16240036,16232511,16234057,16226457,16225826,16235873,16233903,16225359,16237100,16245204,16237568,16243841,16232194,16240389,16223778,16230937,16239006,16244522,16224988,16233336,16248186,16218949,16244881,16238595,16226746,16235588,16224346,16230854,16229927,16245707,16227969,16226800,16223830,16224006,16225590,16219947,16238379,16215130,16228048,16242455,16233330,16223537,16224209,16219153,16226830,16221579,16244994,16225832,16218393,16232863,16230476,16230067,16226928,16242090,16236268,16236533,16216647,16245330,16233898,16229539,16223278,16217339,16223651,16238416,16218986,16226303,16225532,16233222,16234419,16220709,16219547,16231300,16243079,16225692,16232378,16218333,16229619,16215960,16238720,16225918,16221755,16230810,16215788,16243875,16226429,16245411,16219570,16244350,16244908,16229541,16220299,16241376,16216612,16224367,16221924,16242066,16226010,16226521,16221188,16244039,16218693,16233961,16238522,16226251,16223921,16219395,16216065,16230842,16226870,16234632,16225638,16220267,16230944,16227596,16236416,16232258,16232018,16243100,16242978,16231937,16235842,16244968,16242917,16228788,16232758,16222530,16226495,16229720,16242773,16227130,16220376,16242384,16231418,16227513,16235443,16228029,16215363,16221836,16226294,16238619,16239543,16231806,16235519,16220666,16243097,16227520,16218084,16241684,16236214,16225854,16245383,16242475,16216329,16244235,16229257,16238461,16235404,16241923,16238143,16231909,16234901,16224849,16223597,16231440,16223432,16224238,16237940,16245642,16236593,16232905,16245198,16236468,16226235,16227276,16222537,16233368,16236053,16231456,16235160,16216524,16227745,16234208,16230910,16235460,16242954,16221563,16221771,16217241,16229615,16237090,16239010,16224725,16222715,16229268,16242236,16238891,16242146,16223973,16223936,16235886,16243498,16215328,16246409,16225233,16232577,16234520,16229828,16218976,16230337,16220262,16235849,16235823,16228317,16228160,16236404,16234734,16236778,16235436,16240006,16226835,16226802,16232410,16228615,16216187,16217419,16236359,16215555,16219892,16236108,16235864,16224226,16235391,16238667,16231129,16235520,16238464,16236738,16238279,16231658,16232940,16221132,16224165,16234228,16221177,16237803,16220271,16231324,16222279,16235007,16219758,16231863,16220638,16222280,16220514,16234088,16234043,16216789,16234550,16221850,16230607,16217101,16228215,16232337,16232253,16228154,16228147,16224059,16236123,16225857,16236083,16236345,16226387,16235046,16226091,16235412,16216763,16235122,16234808,16224852,16234774,16218637,16218427,16223902,16227559,16219584,16233945,16233942,16233939,16233850,16227163,16221053,16233457,16226590,16227475,16225383,16232659,16225905,16225830,16232406,16228740,16231575,16215764,16228327,16238251,16218971,16223392,16230666,16218488]
"""
let decoder = JSONDecoder()
let data = Data(jsonString.utf8)
if let array = try? decoder.decode(Array<Int>.self, from: data) {
//Your code to use the array goes here
}
How to use Kotlin to Write a Y-combinator function?
In Kotlin, you should introduce an additional interface G, Otherwise you will get the UNCHECKED_CAST warnings, since Kotlin is a statically typed programming language rather than a dynamic language, for example:
typealias X = (Int) -> Int
typealias F = Function1<X, X>
// v-------------v--- let G reference G recursively
interface G : Function1<G, X>
// v--- create a G from lazy blocking
fun G(block: (G) -> X) = object : G {
// v--- delegate call `block(g)` like as `g(g)`
override fun invoke(g: G) = block(g)
}
fun Y(f: F) = (fun(g: G) = g(g))(G { g -> f({ x -> g(g)(x) }) })
val fact = Y({ rec -> { n -> if (n == 0) 1 else n * rec(n - 1) } })
Another version cast a Function1<G, X> to a G, so it should suppress the UNCHECKED_CAST warnings, for example:
typealias X = (Int) -> Int
typealias F = Function1<X, X>
typealias G = Function1<Any, X>
@Suppress("UNCHECKED_CAST")
// v--- cast `g` to `G`.
fun Y(f: F) = (fun(g: Function1<G, X>) = g(g as G))({ g -> f { x -> g(g)(x) } })
val fact = Y({ rec -> { n -> if (n == 0) 1 else n * rec(n - 1) } })
C# anonymous recursion and Y-combinator performance
This took my interest yesterday. I made some tests, this is my try, I've got some speedup. The simpler the delegate, the faster it goes, but some memoization did the trick.
Time test 1 542 69%
Time test 2 377 99%
Time test 3 558 67%
Time test 4 505 74%
Time test 5 372 100%
Time test 6 374 99%
Time test 7 452 82%
Test code for LinqPad.
void Main()
{
foreach(var t in typeof(test).Assembly.GetTypes().Where(t => t.IsSubclassOf(typeof(test))))
((test)(Activator.CreateInstance(t))).TestMethod();
}
private abstract class test
{
public abstract void TestMethod();
}
private class test1 : test
{
delegate Action<T> Continuation<T>(Continuation<T> r);
//[TestMethod]
//The fixed point operator, very slow also.
public override void TestMethod()
{
IObject root = BuildComposite();
Performance.Measure(1000000, () =>
{
Apply(root, h => t =>
{
foreach (IObject item in t.Children)
{
//Console.WriteLine(item.Name);
h(item);
}
});
}, "Time " + this.GetType().Name);
}
private static void Apply(IObject root, Func<Action<IObject>, Action<IObject>> g)
{
Continuation<IObject> action = c => thing => { g(c(c))(thing); };
Action<IObject> target = action(action);
target(root);
}
}
private class test2 : test
{
delegate void Continuation<T>(Continuation<T> r, T n);
//[TestMethod]
//Without curry, curring makes things go slow.
public override void TestMethod()
{
var root = BuildComposite();
Performance.Measure(1000000, () =>
{
Apply(root, (c, thing) =>
{
foreach (var item in thing.Children)
{
//Console.WriteLine(item.Name);
c(c, item);
}
});
}, "Time " + this.GetType().Name);
}
void Apply(IObject root, Continuation<IObject> f)
{
f(f, root);
}
}
private class test3 : test
{
//[TestMethod]
//Another common definition found on web, this is worse of then all.
//https://stackoverflow.com/questions/4763690/alternative-y-combinator-definition
public override void TestMethod()
{
var root = BuildComposite();
Performance.Measure(1000000, () =>
{
Y<IObject, int>(f => thing =>
{
foreach (var item in thing.Children)
{
//Console.WriteLine(item.Name);
f(item);
}
return 0;
})(root);
}, "Time " + this.GetType().Name);
}
public delegate TResult SelfApplicable<TResult>(SelfApplicable<TResult> r);
public static TResult U<TResult>(SelfApplicable<TResult> r)
{
return r(r);
}
public static Func<TArg1, TReturn> Y<TArg1, TReturn>(Func<Func<TArg1, TReturn>, Func<TArg1, TReturn>> f)
{
return U<Func<TArg1, TReturn>>(r => arg1 => f(U(r))(arg1));
}
}
private class test4 : test
{
//[TestMethod]
//Simpler definition, taken from this SO.
//This uses inherent compiler recursion, lets see if it speed things up.
//https://stackoverflow.com/questions/4763690/alternative-y-combinator-definition
public override void TestMethod()
{
var root = BuildComposite();
Performance.Measure(1000000, () =>
{
Y<IObject, int>(f => thing =>
{
foreach (var item in thing.Children)
{
//Console.WriteLine(item.Name);
f(item);
}
return 0;
})(root);
}, "Time " + this.GetType().Name);
}
public static Func<TArg1, TReturn> Y<TArg1, TReturn>(Func<Func<TArg1, TReturn>, Func<TArg1, TReturn>> f)
{
return f(n => Y(f)(n));
}
}
private class test5 : test
{
//[TestMethod]
//Simple way to recurse, is also the fastest
//but then its no more an anonymous lambda.
//This defeats the game purpose.
public override void TestMethod()
{
var root = BuildComposite();
Action<IObject> a = null;
a = thing =>
{
foreach (var item in thing.Children)
{
//Console.WriteLine(item.Name);
a(item);
}
};
Performance.Measure(1000000, () =>
{
a(root);
}, "Time " + this.GetType().Name);
}
}
private class test6 : test
{
//[TestMethod]
//Reference test, direct method call
//There should be no way to get faster than this.
public override void TestMethod()
{
var root = BuildComposite();
Performance.Measure(1000000, () =>
{
a(root);
}, "Time " + this.GetType().Name);
}
public static void a(IObject thing)
{
foreach (var item in thing.Children)
{
//Console.WriteLine(item.Name);
a(item);
}
}
}
private class test7 : test
{
//[TestMethod]
//Lets try some memoization.
public override void TestMethod()
{
var root = BuildComposite();
Performance.Measure(1000000, () =>
{
Y<IObject, int>.Combinator(f => thing =>
{
foreach (var item in thing.Children)
{
//Console.WriteLine(item.Name);
f(item);
}
return 0;
})(root);
}, "Time " + this.GetType().Name);
}
private class Y<TArg1, TReturn>
{
public static Func<TArg1, TReturn> Combinator(Func<Func<TArg1, TReturn>, Func<TArg1, TReturn>> f)
{
return f(n =>
{
if (memoized == null) memoized = Combinator(f);
return memoized(n);
});
}
private static Func<TArg1, TReturn> memoized;
}
}
private interface IObject
{
List<IObject> Children { get; }
}
private class CObject : IObject
{
private int lvl;
public CObject(int lvl)
{
this.lvl = lvl;
}
public List<IObject> Children
{
get
{
var l = new List<IObject>() { BuildComposite(lvl + 1) };
if (lvl > 2) l.Clear();
return l;
}
}
}
private static IObject BuildComposite()
{
return new CObject(0);
}
private static IObject BuildComposite(int lvl)
{
return new CObject(lvl);
}
private class Performance
{
public static void Measure(int count, Action a, string msg)
{
using(new WallClock(msg))
Enumerable.Range(1, count).ToList().ForEach(_ => a());
}
}
private class WallClock : IDisposable
{
private string name;
private Stopwatch w;
public WallClock(string name)
{
this.name = name;
w = Stopwatch.StartNew();
}
public void Dispose()
{
w.Stop();
Console.WriteLine(name + " : " + w.ElapsedMilliseconds);
}
}
references
http://mikehadlow.blogspot.com.br/2009/03/recursive-linq-with-y-combinator.html
Alternative Y combinator definition
http://blogs.msdn.com/b/wesdyer/archive/2007/02/02/anonymous-recursion-in-c.aspx
http://www.justinshield.com/2011/06/recursive-lambda-expressions-in-c-using-ycombinator/
Writing a Swift function that returns itself
Let's try to write such a thing.
func f() {
return f
}
Now the compiler complains because f is not declared to return anything when it does return something.
Okay, let's try to add a return value type i.e. A closure that accepts no parameters and return nothing.
func f() -> (() -> ()) {
return f
}
Now the compiler complains that f is () -> (() -> ()), and so cannot be converted to () -> ().
We should edit the declaration to return a () -> (() -> ()), right?
func f() -> (() -> (() -> ())) {
return f
}
Now f becomes a () -> (() -> (() -> ())), which cannot be converted to a () -> (() -> ())!
See the pattern now? This will continue forever.
Therefore, you can only do this in a type-unsafe way, returning Any:
func f() -> Any { return f }
Usage:
func f() -> Any {
print("Hello")
return f
}
(f() as! (() -> Any))()
The reason why this is possible in python is exactly because Python is weakly typed and you don't need to specify the return type.
Note that I do not encourage you to write this kind of code in Swift. When you code in Swift, try to solve the problem with a Swift mindset. In other words, you should think of another way of solving the problem that does not involve a function like this.
Related Topics
Argument for Generic Parameter Could Not Be Inferred
Can You Give Uistackview Borders
Difference Between Awakefromnib() and Viewdidload() in Swift
Use of Undeclared Type 'Viewcontroller' When Unit Testing My Own Viewcontroller in Swift
Strange Error Nw_Protocol_Get_Quic_Image_Block_Invoke Dlopen Libquic Failed
Can't Pass Date to Nspredicate(Format: ...) Without "As Cvararg"
Views Compressed by Other Views in Swiftui VStack and List
Swift 3 Get Start Index (As Int) of Substring
Insertion-Order Dictionary (Like Java's Linkedhashmap) in Swift
Example of Dispatch_Once in Swift
How to Use Unsafemutablerawpointer to Fill an Array
Swift: Popover Dismiss Callback
Local Notification While App Not Running