Преобразование функции Полиморфного косинуса Хаскелла в F #

Question

Я пытаюсь преобразовать некоторый код на Haskell в F #, но у меня возникли некоторые проблемы, поскольку Haskell по умолчанию ленив, а F # - нет.Я также все еще изучаю свой путь F #.Ниже приведена полиморфная функция косинуса в Haskell с довольно хорошей производительностью.Я хочу попытаться сохранить те же или лучшие параметры производительности в F #.Я хотел бы видеть версию F # List и F # Seq версию, поскольку версия Seq больше походила бы на ленивый Haskell, но версия List, вероятно, работала бы лучше.Спасибо за любую помощь.

Эффективность: количество использованных арифметических операций пропорционально количеству терминов в серии

Пробел: используется постоянное пространство, не зависящее от количества терминов

takeThemTwoByTwo xs =
    takeWhile (not . null) [take 2 ys | ys <- iterate (drop 2) xs]

products xss = [product xs | xs <- xss]

pairDifferences xs =
    [foldr (-) 0 adjacentPair | adjacentPair <- takeThemTwoByTwo xs]

harmonics x = [x/(fromIntegral k) | k <- [1 ..]]

cosineTerms = scanl (*) 1 . products . takeThemTwoByTwo . harmonics

cosine = foldl (+) 0 . pairDifferences .
    take numberOfTerms . cosineTerms

Answer 1

Вот моя попытка, если вам лень читать:

let harmonics x = 
    Seq.initInfinite(fun i -> - x*x/(float ((2*i+1)*(2*i+2))))

let cosineTerms = Seq.scan (*) 1.0 << harmonics

let cosine numberOfTerms = Seq.sum << Seq.take numberOfTerms << cosineTerms

Мне трудно понять, что вы вычисляете cosine в радианах, используя ряд Тейлора:

косинус (х) = 1 - х ² / 2! + х ⁴ / 4! - х ⁶ / 6! + ...

Позвольте мне описать, что вы делаете:

1. Создать бесконечную последовательность x/k, где k - целое число, начиная с 1.

2. Разделите вышеуказанную последовательность на две части и отсканируйте, умножив на начальное число 1, чтобы получить последовательность x ² / ((2k-1) * (2k)) ( за исключением 1 в начале).

3. Снова разбить новую последовательность на блоки по два, чтобы получить различия в виде x ^4k-4 / ((4k-4)!) - x ^4k-2 / ((4k-2)!) И суммируйте их все, чтобы получить окончательный результат.

Поскольку разделение последовательностей в F # может оказаться неэффективным, а функция takeThemTwoByTwo не является необходимой, я выбрал другой подход:

1. Создать бесконечную последовательность из - x ² / ((2k-1) * (2k)), где k - целое число, начиная с 1.
2. Сканирование последовательности путем умножения на начальное число 1; мы получаем последовательность (-1) ^k * x ^2k / ((2k)!).
3. Суммируйте все элементы, чтобы получить окончательный результат.

Вышеуказанная программа является прямым переводом моего описания, лаконичным и простым. Вычисление cosine с numberOfTerms = 200000 итерациями занимает 0,15 секунды на моем компьютере; Я полагаю, это достаточно эффективно для вашей цели.

Кроме того, версию List должно быть легко перевести с этой.

UPDATE:

Хорошо, я виноват в том, что недооценил часть вопроса о полиморфизме. Я сосредоточился больше на части производительности. Вот полиморфная версия (близкая к версии float):

let inline cosine n (x: ^a) = 
    let one: ^a = LanguagePrimitives.GenericOne
    Seq.initInfinite(fun i -> LanguagePrimitives.DivideByInt (- x*x) ((2*i+1)*(2*i+2)))
    |> Seq.scan (*) one
    |> Seq.take n
    |> Seq.sum

Seq.initInfinite менее мощен, чем Seq.unfold в ответе @kvb. Я держу это, чтобы сделать вещи простыми, потому что n в любом случае находится в диапазоне int.

Answer 2

Пад ответ хороший, но не полиморфный.В общем, в F # создание таких определений значительно реже, чем в Haskell (и это немного сложно).Вот один из подходов:

module NumericLiteralG =
    let inline FromZero() = LanguagePrimitives.GenericZero
    let inline FromOne() = LanguagePrimitives.GenericOne    

module ConstrainedOps =
    let inline (~-) (x:^a) : ^a = -x
    let inline (+) (x:^a) (y:^a) : ^a = x + y
    let inline (*) (x:^a) (y:^a) : ^a = x * y
    let inline (/) (x:^a) (y:^a) : ^a = x / y

open ConstrainedOps

let inline cosine n x = 
    let two = 1G + 1G
    Seq.unfold (fun (twoIp1, t) -> Some(t, (twoIp1+two, -t*x*x/(twoIp1*(twoIp1+1G))))) (1G,1G)
    |> Seq.take n
    |> Seq.sum

Answer 3

Как писал Пад, это, по-видимому, расширение серии Тейлора cos ( x ) примерно x = 0:

косинус (x) = 1 - x² / 2! + х⁴ / 4! - х⁶ / 6! + ...

Итак, ваш вопрос - это вопрос XY: вы представили решение, а не поставили проблему. Вместо этого, представление проблемы значительно упрощает ее решение.

Давайте начнем с написания float -специфической версии на F #:

let cosine n x =
  let rec loop i q t c =
    if i=n then c else
      loop (i + 1) (q + 10 + 8*i) (-t * x * x / float q) (c + t)
  loop 0 2 1.0 0.0

Например, мы можем вычислить 1M слагаемых расширения x = 0.1:

cosine 1000000 0.1

Лучший способ сделать эту полиморфную в F # - это параметризовать функцию по операторам, которые она использует, и пометить ее как inline, чтобы снять издержки производительности при этой параметризации:

let inline cosine zero one ofInt ( ~-. ) ( +. ) ( *. ) ( /. ) n x =
  let rec loop i q t c =
    if i=n then c else
      loop (i + 1) (q + 10 + 8*i) (-.t *. x *. x /. ofInt q) (c +. t)
  loop 0 2 one zero

Теперь мы можем вычислить 1M терминов, используя float, как это, что так же быстро, как и раньше:

cosine 0.0 1.0 float ( ~- ) (+) (*) (/) 1000000 0.1

Но мы также можем сделать с одинарной точностью float:

cosine 0.0f 1.0f float32 ( ~- ) (+) (*) (/) 1000000 0.1f

И произвольная точность рациональна:

cosine 0N 1N BigNum.FromInt (~-) (+) (*) (/) 10 (1N / 10N)

И даже символично:

type Expr =
  | Int of int
  | Var of string
  | Add of Expr * Expr
  | Mul of Expr * Expr
  | Pow of Expr * Expr

  static member (~-) f = Mul(Int -1, f)
  static member (+) (f, g) = Add(f, g)
  static member (*) (f, g) = Mul(f, g)
  static member (/) (f, g) = Mul(f, Pow(g, Int -1))

cosine (Int 0) (Int 1) Int (~-) (+) (*) (/) 3 (Var "x")

Чтобы сделать это быстрее, поднимите общее подвыражение -x*x из loop.