Haskell-> F#: Решето Токаря
Я читал на различных алгоритмах просеивания, когда я наткнулся на своего рода улучшенную версию Решета Эратосфена, названного Решетом Euler's. Согласно Википедии существует реализация немного отличающейся версии идеи (названа Решетом Токаря) в Haskell.
Теперь я пытаюсь понять то, что точно делает данный фрагмент кода и я думаю, что у меня есть он, но теперь я хотел перевести код в F# и не иметь действительно никакой идеи, где запустить. Мое основное беспокойство - то, что, кажется, нет функции к "substract" двух последовательностей.
Вот код:
import Data.OrdList (minus)
primes = euler [2..]
euler (p : xs) = p : euler (xs `minus` map (*p) (p : xs))
Как это было бы реализовано в F#? Это даже возможно?
3 ответа
Это не указатели функций (а указатели в JS изначально отсутствуют). Функции в JS могут быть анонимными и являются объектами первого класса. Следовательно,
function () { alert("A"); }
создает анонимную функцию, которая предупреждает «A» при выполнении;
var bar = function () { alert("A"); };
назначить эту функцию панели;
var foo = bar;
назначить foo панели, которая является функцией «A».
bar = function () { alert("B"); };
повторная привязка строки к анонимной функции «B». Это не повлияет на foo или другую функцию «A».
foo();
Вызовите функцию, сохраненную в foo, которая является функцией «A».
На самом деле в языках, где есть функциональные точки, например C, это также не повлияет на foo . Я не знаю, откуда у вас идея получить «Б» при переназначении.
void A(void) { printf("A\n"); }
void B(void) { printf("B\n"); }
typedef void(*fptr_t)(void);
fptr_t foo = A;
fptr_t bar = foo;
bar = B;
foo(); // should print "A"
Имеется ли в каталоге foo файл с именем __ init __ .py ? Если нет, то питон не узнает фу как пакет питона.
Для получения дополнительной информации см. раздел о пакетах в руководстве python.
-121--738823-Если вы хотите вычислить такие вещи, как слияния/различия бесконечных списков, как это делает Haskell, тип LazyList (найденный внутри F # power пакета) обращается к виду.
Это делает для очень подробный код, как перевод ниже:
#r "FSharp.PowerPack.dll"
//A lazy stream of numbers, starting from x
let rec numsFrom x = LazyList.consDelayed x (fun () -> numsFrom (x+1))
//subtracts L2 from L1, where L1 and L2 are both sorted(!) lazy lists
let rec lazyDiff L1 L2 =
match L1,L2 with
| LazyList.Cons(x1,xs1),LazyList.Cons(x2,xs2) when x1<x2 ->
LazyList.consDelayed x1 (fun () -> lazyDiff xs1 L2)
| LazyList.Cons(x1,xs1),LazyList.Cons(x2,xs2) when x1=x2 ->
lazyDiff xs1 L2
| LazyList.Cons(x1,xs1),LazyList.Cons(x2,xs2) when x1>x2 ->
lazyDiff L1 xs2
| _ -> failwith "Should not occur with infinite lists!"
let rec euler = function
| LazyList.Cons(p,xs) as LL ->
let remaining = lazyDiff xs (LazyList.map ((*) p) LL)
LazyList.consDelayed p (fun () -> euler remaining)
| _ -> failwith "Should be unpossible with infinite lists!"
let primes = euler (numsFrom 2)
с
> primes |> Seq.take 15 |> Seq.toList;;
val it : int list = [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47]
Обратите внимание, что я добавил два failwith предложения, чтобы удержать компилятор от жалобы на неполное совпадение, даже если мы знаем, что все списки в вычислении (лениво) бесконечны.
Вы можете сделать это с помощью seq . И поскольку вы получили минус , сам euler такой же, как и в Haskell.
let rec minus xs ys =
seq {
match Seq.isEmpty xs, Seq.isEmpty ys with
| true,_ | _,true -> yield! xs
| _ ->
let x,y = Seq.head xs, Seq.head ys
let xs',ys' = Seq.skip 1 xs, Seq.skip 1 ys
match compare x y with
| 0 -> yield! minus xs' ys'
| 1 -> yield! minus xs ys'
| _ -> yield x; yield! minus xs' ys
}
let rec euler s =
seq {
let p = Seq.head s
yield p
yield! minus (Seq.skip 1 s) (Seq.map ((*) p) s) |> euler
}
let primes = Seq.initInfinite ((+) 2) |> euler
С последовательностями вы получаете гораздо больше конкуренции, сохраняя последовательность:
let rec euler s =
seq {
let s = Seq.cache s
let p = Seq.head s
yield p
yield! minus (Seq.skip 1 s) (Seq.map ((*) p) s) |> euler
}