F # Как я должен думать о разделении элементов в последовательностях?

Question

Извинения за новый вопрос. Я пытаюсь изменить свою умственную парадигму с процедурной на функциональную.

Например, предположим, у меня есть список имен, которые я хочу напечатать примерно так: «Джон, Пол, Джордж и Ринго». Но этот код не удовлетворяет:

let names = [ "John"; "Paul"; "George"; "Ringo" ]
names |> Seq.iter (fun s -> printf "%s, " s)

Мой процедурный инстинкт состоит в том, чтобы искать способ ввести предикат в эту лямбду, чтобы он мог переходить между "," или "и" или "." В зависимости от того, где мы находимся при итерации последовательности. Я думаю, что это неправильно, но я чувствую, что правильно.

Было бы лучше разбить последовательность на части?

В этом случае кажется, что мы хотим разделить последовательность на части, соответствующие различным поведениям разделителя. Мы хотим разделить его в конце, поэтому мы не можем использовать Seq. Но вместо этого мы можем использовать List.splitAt. * ​​1010 *

let start, ending = List.splitAt (names.Length - 1) names
let penultimate, last = List.splitAt 1 ending
start |> Seq.iter (fun s -> printf "%s, " s)
penultimate |> Seq.iter (fun s -> printf "%s, and " s)
last |> Seq.iter (fun s -> printf "%s. " s)

Это праведный подход? Есть ли лучшее решение, которое я упустил? Думал ли я в правильном направлении?

Answer 1

Основные приемы упомянуты в принятом ответе : деконструкция проблемы и разделение проблем. Элемент либо отсутствует, либо за элементом следует либо ., , and, либо ,, в зависимости от его положения относительно конца входной последовательности.

Предполагая, что вход имеет тип string list, это может быть довольно хорошо выражено рекурсивным определением функции сопоставления с образцом, заключенным в список выражение последовательности для обеспечения рекурсии хвоста. Совпадение ничего не делает, если вход пустой, поэтому он возвращает пустой список; он возвращает подсписок для другого завершающего случая, в противном случае он добавляет к подсписку результаты рекурсии.

Объединение в качестве требуемого целевого типа string - это отдельный, последний шаг, как предлагается в другой ответ .

let rec seriesComma xs = [
    match xs with
    | [] -> ()
    | [x] -> yield! [x; "."]
    | x::[y] -> yield! [x; ", and "]; yield! seriesComma [y]
    | x::xs -> yield! [x; ", "]; yield! seriesComma xs ]

["Chico"; "Harpo"; "Groucho"; "Gummo"; "Zeppo"]
|> seriesComma |> String.concat ""
// val it : string = "Chico, Harpo, Groucho, Gummo, and Zeppo."

Answer 2

Seq.Reduce - это самый простой способ составить список с разделителями, но включение «и» перед последним элементом добавляет некоторую сложность. Ниже я показываю способ сделать это в два этапа, но рекурсивный подход в принятом ответе, вероятно, больше соответствует парадигме функционального программирования.

let names = [ "John"; "Paul"; "George"; "Ringo" ]
let delimitedNames = names |> Seq.reduce (fun x y -> sprintf "%s, %s" x y)

let replaceLastOccurrence (hayStack: string) (needle: string) (newNeedle: string) =
    let idx = hayStack.LastIndexOf needle
    match idx with
    | -1 -> hayStack
    | _ -> hayStack.Remove(idx, needle.Length).Insert(idx, newNeedle)

replaceLastOccurrence delimitedNames "," ", and"

См. https://msdn.microsoft.com/en-us/visualfsharpdocs/conceptual/seq.reduce%5B%27t%5D-function-%5Bfsharp%5D?f=255&MSPPError=-2147217396

Answer 3

Общий подход, который я использую для решения подобных проблем, состоит в том, чтобы разбить их на более мелкие части и решить индивидуально:

• пустой список [] приводит к ""
• один элемент ["a"] приводит к "a."
• два элемента [ "a"; "b" ] результат "a and b."
• больше элементов (то есть a :: rest) приводит к "a, " + takeCareOf rest, где takeCareOf следует вышеприведенным правилам. Обратите внимание, что нам не нужно знать длину полного списка.

Приведенный выше рецепт напрямую переводится на F # (и функциональные языки в целом):

let rec commaAndDot' = function
| [] -> ()
| [ a ] -> printfn "%s." a
| a :: [ b ] -> printfn "%s and %s." a b
| a :: rest -> printf "%s, " a; commaAndDot' rest

Мы уже закончили? Нет, commaAndDot' нарушает Принцип единой ответственности , потому что функция реализует нашу «бизнес-логику» и выводов на консоль. Давайте исправим это:

let rec commaAndDot'' = function
| [] -> ""
| [ a ] -> sprintf "%s." a
| a :: [ b ] -> sprintf "%s and %s." a b
| a :: rest -> sprintf "%s, " a + commaAndDot'' rest

В качестве дополнительного преимущества мы можем теперь вызывать функцию параллельно, и вывод больше не перепутывается.

Мы уже закончили? Нет, функция выше не является хвостовой рекурсивной (нам нужно вычислить commaAndDot'' rest перед конкатенацией ее к текущему результату) и взорвать стек для больших списков. Стандартный подход к решению этой проблемы - ввести аккумулятор acc:

let  commaAndDot''' words =
    let rec helper acc = function
    | [] -> acc
    | [ a ] -> sprintf "%s%s." acc a
    | a :: [ b ] -> sprintf "%s%s and %s." acc a b
    | a :: rest ->  helper (acc + sprintf "%s, " a) rest
    helper "" words

Мы уже закончили? Нет, commaAndDot''' создает много строк для промежуточных результатов. Благодаря тому, что F # не является чистым языком, мы можем использовать локальную (частную, ненаблюдаемую) мутацию для оптимизации памяти и скорости:

let  commaAndDot words =
    let sb = System.Text.StringBuilder()
    let rec helper = function
    | [] -> sb
    | [ a ] -> sprintf "%s." a |> sb.Append
    | a :: [ b ] -> sprintf "%s and %s." a b |> sb.Append
    | a :: rest ->
        sprintf "%s, " a |> sb.Append |> ignore
        helper rest
    helper words |> string

Мы уже закончили? Вероятно ... по крайней мере, это то, что я бы посчитал идиоматическим F # и с радостью совершил. Для дальнейшей оптимизации (например, Append раздельных запятых и точек или изменения порядка шаблонов) я бы сначала написал микротесты перед тем, как жертвовать удобочитаемостью.

Все версии генерируют одинаковый вывод:

commaAndDot []                          // ""
commaAndDot [ "foo" ]                   // "foo."
commaAndDot [ "foo"; "bar" ]            // "foo and bar."
commaAndDot [ "Hello"; "World"; "F#" ]  // "Hello, World and F#."

Обновление : SCNR, создан эталонный тест ... результаты приведены ниже как фрагмент HTML (для хороших табличных данных).

BuilderOpt - версия StringBuilder с корпусом [], перемещенным вниз; BuilderChained - это связанные вызовы Append, например, sb.Append(a).Append(" and ").Append(b) и BuilderFormat, например, sb.AppendFormat("{0} and {1}", a, b). Полный исходный код доступно.

Как и ожидалось, «более простые» версии работают лучше для небольших списков, чем больше список, тем лучше BuilderChained. Concat работает лучше, чем я ожидал, но не выдает правильного вывода (отсутствует ".", Отсутствует один регистр). Урожай становится довольно медленным ...

<!DOCTYPE html>
<html lang='en'>
<head>
<meta charset='utf-8' />
<title>Benchmark.CommaAndDot</title>

<style type="text/css">
	table { border-collapse: collapse; display: block; width: 100%; overflow: auto; }
	td, th { padding: 6px 13px; border: 1px solid #ddd; }
	tr { background-color: #fff; border-top: 1px solid #ccc; }
	tr:nth-child(even) { background: #f8f8f8; }
</style>
</head>
<body>
<pre><code>
BenchmarkDotNet=v0.11.1, OS=Windows 10.0.16299.726 (1709/FallCreatorsUpdate/Redstone3)
Intel Core i7 CPU 950 3.07GHz (Nehalem), 1 CPU, 8 logical and 4 physical cores
Frequency=2998521 Hz, Resolution=333.4977 ns, Timer=TSC
  [Host]     : .NET Framework 4.7.2 (CLR 4.0.30319.42000), 64bit LegacyJIT-v4.7.3190.0 DEBUG
  DefaultJob : .NET Framework 4.7.2 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.3190.0

Метод	Детализация	Среднее	Ошибка	StdDev	Медиана	Чешуйчатый	ScaledSD
Concat	0	39,905 нс	0,0592 нс	0,0494 нс	39,906 нс	1,02	0,11
Выход	0	27,235 нс	0,0772 нс	0,0603 нс	27,227 нс	0,69	0,07
Аккумулятор	0	1,956 нс	0,0109 нс	0,0096 нс	1,954 нс	0,01
Строитель	0	32,384 нс	0,2986 нс	0,2331 нс	32,317 нс	0,82	0,09
BuilderOpt	0	33,664 нс	1,0371 нс	0,9194 нс	33,402 нс	0,86	0,09
BuilderChained	0	39,671 нс	1,20997 нс	3,5669 нс	41,339 нс	1,00	0,00
BuilderFormat	0	40,276 нс	0,8909 нс	1,8792 нс	39,494 нс	1,02	0,12
Конкат	1	153,116 нс	1,1592 нс	0,9050 нс	152,706 нс	0,87	0,01
Выход	1	154,522 нс	0,2890 нс	0,2256 нс	154,479 нс	0,88	0,00
Аккумулятор	1	223,342 нс	0,3678 нс	0,2872 нс	223,412 нс	1,27	0,00
Строитель	1	232,194 нс	0,2951 нс	0,2465 нс	232,265 нс	1,32	0,00
BuilderOpt	1	232,016 нс	0,5654 нс	0,4722 нс	232,170 нс	1,31	0,00
BuilderChained	1	176,473 нс	0,3918 нс	0,3272 нс	176,341 нс	1,00	0,00
BuilderFormat	1	219,262 нс	6,7995 нс	6,3603 нс	217,003 нс	1,24	0,03
Конкат	10	1 284,042 нс	1,7035 нс	1,4225 нс	1 283,443 нс	1,68	0,05
Выход	10	6532,667 нс	12,6169 нс	10,5357 нс	6533,50 нс	8,55	0,24
Аккумулятор	10	2701,483 нс	4,8509 нс	4,5376 нс	2700,208 нс	3,54	0,10
Строитель	10	1 865,668 нс	5,0275 нс	3,9252 нс	1 866,920 нс	2,44	0,07
BuilderOpt	10	1 820,402 нс	2,753 нс	2,3258 нс	1 820,464 нс	2,38	0,07
BuilderChained	10	764,334 нс	19,8528 нс	23,6334 нс	756,988 нс	1,00	0,00
BuilderFormat	10	1 177,186 нс	1,9584 нс	1,6354 нс	1 177,897 нс	1,54	0,04
Конкат	100	25 579,773 нс	824,1504 нс	688,2028 нс	25 288,873 нс	5,33	0,14
Выход	100	421 872,560 нс	902.5023 нс	753,6302 нс	421 782,071 нс	87,87	0,23
Аккумулятор	100	80 579,168 нс	227,7392 нс	177.8038 нс	80 547,868 нс	16,78	0,05
Строитель	100	15 047,790 нс	26,2248 нс	21,8989 нс	15 048,903 нс	3,13	0,01
BuilderOpt	100	15,287.117 нс	39,8679 нс	31.1262 нс	15 293,739 нс	3,18	0,01
BuilderChained	100	4 800,966 нс	11,3614 нс	10,0716 нс	4 801,450 нс	1,00	0,00
Формат Builder	100	8 382,896 нс	87,8963 нс	68,6236 нс	8 368 400 нс	1,75	0,01

Answer 4

Я предпочитаю использовать String.concat:

let names = [ "John"; "Paul"; "George"; "Ringo" ]
names
|> List.mapi (fun i n -> if i = names.Length - 1 && i > 0 then "and " + n else n)
|> String.concat ", "
|> printfn "%s"

Answer 5

Ну, более функционально выглядящее решение может быть примерно таким:

let names = [ "John"; "Paul"; "George"; "Ringo" ]

names
|> Seq.tailBack
|> Seq.iter (fun s -> printf "%s, " s)

names
|> Seq.last
|> fun s -> printf "and %s" s

Где tailBack может быть определено в некоторых SequenceExtensions.fs как

module Seq 

let tailBack seq =
    seq
    |> Seq.rev
    |> Seq.tail
    |> Seq.rev

Таким образом, вы не слишком много работаете с индексами, переменными и всем этим процедурным материалом.

В идеале вы должны использовать параметры здесь, например

names
|> Seq.tryLast
|> Option.iter (fun s -> printf "and %s" s)

При этом вы также избежите возможных исключений аргументов. Но варианты в функциональном программировании - это еще одна (хорошая) концепция, чем последовательности.

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