Модифицированный map2 (без усечения списков) в F # - как это сделать идиоматически? - PullRequest
Новая
       13

Модифицированный map2 (без усечения списков) в F # - как это сделать идиоматически?

1 голос
/ 15 мая 2010

Я бы хотел переписать такую ​​функцию на F #: 

zipWith' :: (a -> b -> c) -> (a -> c) -> (b -> c) -> [a] -> [b] -> [c]
zipWith' _ _ h []     bs     = h `map` bs
zipWith' _ g _ as     []     = g `map` as
zipWith' f g h (a:as) (b:bs) = f a b:zipWith f g h as bs

Моя первая попытка была: 

let inline private map2' (xs : seq<'T>) (ys : seq<'U>) (f : 'T -> 'U -> 'S) (g : 'T -> 'S) (h : 'U -> 'S) =
    let xenum = xs.GetEnumerator()
    let yenum = ys.GetEnumerator()
    seq {
        let rec rest (zenum : IEnumerator<'A>) (i : 'A -> 'S) =
            seq {
                yield i(zenum.Current)
                if zenum.MoveNext() then yield! (rest zenum i) else zenum.Dispose()
            }
        let rec merge () =
            seq {
                if xenum.MoveNext()
                then
                    if yenum.MoveNext()
                    then yield (f xenum.Current yenum.Current); yield! (merge ())
                    else yenum.Dispose(); yield! (rest xenum g)
                else
                    xenum.Dispose()
                    if yenum.MoveNext()
                    then yield! (rest yenum h)
                    else yenum.Dispose()
            }
        yield! (merge ())
    }

Однако это вряд ли можно считать идиоматическим.Я слышал о LazyList, но нигде не могу его найти.

Ответы [ 3 ]

3 голосов
/ 15 мая 2010

Как упоминал Брайан, F # предоставляет обычный ленивый список в стиле Haskell в PowerPack, так что вы можете использовать его. К сожалению, не существует хорошего способа выразить подобные вещи с помощью стандартных выражений последовательности F #, потому что они могут выражать только вычисления, которые читают данные из одной последовательности, используя for (в вашем случае вам нужно будет читать из нескольких последовательностей ).

Однако можно написать вычисление (аналогично seq { .. }) для работы с IEnumerator<T> - это обязательное вычисление, которое изменяет счетчик за кулисами, но его можно использовать для шаблонов кодирования, когда seq недостаточно хорош Я планирую написать об этом в блоге, но пока вы можете получить его здесь (код также включает решение вашей проблемы).

Тогда вы можете написать это: 

// Zip using specified functions for sequences 
let zipWithFun f g h (a:seq<_>) (b:seq<_>) = 
  // Local helper function that works with iterators (xs and ys)
  let rec zipWithFunE xs ys = iter {
    // Try to get first element from both iterators (mutates the iterators!)
    let! x = xs
    let! y = ys
    match x, y with 
    | Some(x), Some(y) -> 
        // If both produced value, then combine values using 'f' & continue
        yield f (x, y)
        yield! zipWithFunE xs ys 
    // If only one produced value, yield the value and then return the
    // remaining values projected using one of the functions
    | Some(rest), _ ->
        yield g rest
        yield! ys |> Enumerator.map g
    | _, Some(rest) ->
        yield g rest
        yield! ys |> Enumerator.map g
    | _ -> () }

  // Construct a 'seq' value from a function that processes enumerators
  Enumerator.toSeq (fun () -> 
    zipE (a.GetEnumerator()) (b.GetEnumerator()))

Основная часть кода в значительной степени копирует структуру исходного решения Haskell, что делает этот подход очень привлекательным, но вы все равно можете использовать последовательности напрямую, без копирования данных в какую-либо другую структуру данных.

2 голосов
/ 15 мая 2010

LazyList находится в F # PowerPack . Вам, вероятно, нужно это написать это более элегантно. Учитывая, как хорошо выглядит ваш первый пробный код, я надеюсь, у вас не возникнет проблем при разработке версии LazyList

1 голос
/ 15 мая 2010

Я предлагаю: 

let forever xs =
    Seq.append (Seq.map Some xs) (Seq.initInfinite (fun _ -> None))

let zipWith f g h xs ys =
    Seq.zip (forever xs) (forever ys)
    |> Seq.takeWhile (fun (x, y) -> Option.isSome x || Option.isSome y)
    |> Seq.map ( function
        | (Some x, Some y) -> f x y
        | (Some x, None  ) -> g x
        | (None  , Some y) -> h y
        | _ -> failwith "quite unexpected !" )
...