Podaj element tyle razy, ile chcę

Oct 03 2020

Mam ten kod:

lado ::  [([Char],Int)] -> [[Char]]
lado xs = [a | (a,b) <- xs]

Muszę to wypisać:

> lado [("A",3),("B",2),("C",1)]
["A","B","C","A","B","A"]

Muszę wypisać „A” 3 razy, następnie „B” 2 razy, a następnie „C” 1 raz, ale dostaję tylko to [„A”, „B”, „C”] z tym kodem.

Odpowiedzi

2 WillNess Oct 04 2020 at 18:14

Próbujesz już używać wyrażeń listowych. Użyj ich więcej.

lado ::  [([Char],Int)] -> [[Char]]
lado xs = [a | (a,b) <- xs, b <- [1..b]]

testowanie:

> lado [("A",3),("B",2),("C",1)]
["A","A","A","B","B","C"]

Jak mówi twoje pytanie,

Muszę wypisać „A” 3 razy, następnie „B” 2 razy, a następnie „C” 1 raz

Ale jeśli naprawdę tego ["A","B","C","A","B","A"]chcesz, to

lado ::  [(a,Int)] -> [a]
lado []        = []
lado ((a,1):b) = a : lado b
lado ((a,n):b) = a : lado (b ++ [(a,n-1))])

które można zakodować z unfoldr :: (b -> Maybe (a, b)) -> b -> [a]od Data.List,

lado ::  [(a,Int)] -> [a]
lado xs = unfoldr g $ xs
  where
  g []        = Nothing
  g ((a,1):b) = Just (a, b)
  g ((a,n):b) = Just (a, b ++ [(a,n-1)])

które można emulować z Prelude iterate :: (a -> a) -> a -> [a]itp., jak

lado ::  [(a,Int)] -> [a]
lado xs = map (fst . head) . takeWhile ( ... ) . iterate g $ xs
  where
  g []            = []
  g ((a, ... ):b) = b
  g ((a,  n  ):b) = b ++ [(a, ... )]

Testowanie:

> lado [("A",3),("B",2),("C",1)]
["A","B","C","A","B","A"]

Wypełnij puste pola, ...aby zadziałało.

jak zauważa @dfeuer , powtarzające się dołączanie singletonów na końcu listy jest szkodliwe dla ogólnej wydajności. Dzięki jego wkładowi i dyskusji, w tym dwóm odpowiedziom i komentarzom tutaj, a nawet istocie na githubie , można temu zaradzić za pomocą zwykłego paradygmatu FP (żeby nie powiedzieć „sztuczki”) budowania listy w odwrotnej kolejności, jak

lado ::  [(a,Int)] -> [a]
lado xs = go (filter ((> 0) . snd) xs) []
  where
  go []       []  =  []
  go []        r  =  go (reverse r) []
  go ((a,1):b) r  =  a : go b r
  go ((a,n):b) r  =  a : go b ((a,n-1):r)

Po zamortyzowaniureverse kosztu całej produkcji spowoduje to dodanie tylko stałego narzutu na każdą pozycję wyjściową.

3 Aplet123 Oct 03 2020 at 21:39

Aby to osiągnąć, możesz użyć rekurencji:

lado :: [(a, Int)] -> [a]
-- base case
lado [] = []
-- take each of the non-zero elements then recurse
lado xs = map fst nonzero ++ lado subtracted
    where
        -- find elements with non-zero count
        nonzero = filter (\x -> snd x > 0) xs
        -- subtract one from the count for each of those elements
        subtracted = map (\(x, n) -> (x, n - 1)) nonzero

1 WillemVanOnsem Oct 03 2020 at 22:25

transpose :: [[a]] -> [[a]]Z [["A", "A", "A"], ["B", "B"], ["C"]]IS:

Prelude Data.List> transpose [["A", "A", "A"], ["B", "B"], ["C"]]
[["A","B","C"],["A","B"],["A"]]

jeśli następnie połączymy je z concat :: [[a]] -> [a], otrzymamy:

Prelude Data.List> concat (transpose [["A", "A", "A"], ["B", "B"], ["C"]])
["A","B","C","A","B","A"]

jeśli w ten sposób możemy stworzyć listę trzech "A", dwóch "B"i jednej "C", to możemy wygenerować taką listę. Generowanie tej listy zostawiam jako ćwiczenie. Możesz używać replicate :: Int -> a -> [a]i używać rozumienia list, lub map :: (a -> b) -> [a] -> [b].

1 dfeuer Oct 04 2020 at 19:44

Bardzo podoba mi się podejście Aplet123 , ale myślę, że można je nieco usprawnić. Co jest z tym nie tak? nonzerojest używany dwukrotnie, co oznacza, że program zrealizuje swoją listę wyników, zamiast łączyć ją z odbiorcami tej listy. Więc za każdym razem, gdy przejdziemy przez rekursję, przydzielimy trzy nowe listy. Czy możemy to naprawić? Zacznijmy od założenia, że argument nie zawiera zer.

-- Assumes all the Ints are positive
lado' :: [(a, Int)] -> [a]
lado' [] = []
lado' xns = map fst xns ++ rest
  where
    rest = lado' [(x, n - 1) | (x, n) <- xns, n /= 1]

To już jest dużo lepsze. Za każdym razem przydziela tylko dwie listy. Ale map fstprzydzieli kilka opcji selektora do umieszczenia na liście. Możemy to naprawić za pomocą innego zrozumienia listy:

-- Assumes all the Ints are positive
lado' :: [(a, Int)] -> [a]
lado' [] = []
lado' xns = start ++ rest
  where
    start = [x | (x, _) <- xns]
    rest = lado' [(x, n - 1) | (x, n) <- xns, n /= 1]

Ładnie i czysto! Ale co, jeśli oryginalna lista zawiera zera? Możemy to odfiltrować z góry:

lado :: [(a, Int)] -> [a]
lado = lado' . filter (\(_, n) -> n > 0)

W przypadku dużej liczby innych niż małe liczby istnieje jeszcze jedna mała nieefektywność: reprezentacja listy par. Mała poprawa:

data IPair a = IPair a !Int

Większe usprawnienie zmieniłoby implementację list:

data IPList a
  = Cons a !Int (IPList a)
  | Nil

Wadą IPListjest to, że musiałbyś porzucić listy składane.

Widzę, że nie możesz używać rekurencji, co jest ... dość głupim wymaganiem. Można zobaczyć, jak obejść to z iterate, takeWhilei concat?

1 LouisWasserman Oct 04 2020 at 18:24

Jeśli nie zależy Ci na wydajności, możesz to załatwić, myślę, że:

lado xs =
  [ str
    | i <- [1..maxCount]
    , (str, j) <- xs
    , j >= i ]
  where
    maxCount = maximum (map snd xs)

1 dfeuer Oct 05 2020 at 17:39

Will Ness wymyślił fajne wyrażenie pod względem rotacji:

lado ::  [(a,Int)] -> [a]
lado []        = []
lado ((a,1):b) = a : lado b
lado ((a,n):b) = a : lado (b ++ [(a,n-1))])

Niestety będzie to dość nieefektywne, ponieważ użycie ++dodania elementu na końcu listy wymaga czasu liniowego. Można to naprawić, używając kolejki zamiast listy. Kolejka jest używana w sposób efemeryczny, więc może być bardzo prosta: