Haskell - malé úložky 2.0

[mhb]

Ahoj,

všichni určitě známe s0cketčiny „malé úložky“ - http://s0cketka.blogspot.com/2006/01/ha ... lozky.html. Ty jsou poměrně hezké, ale jejich úložiště statické a jejich počet relativně malý.

Navrhuji tedy všem, kdo v budoucnu budou sedat k počítáči s tím, že mají hezkou (či těžkou) malou úložku na Haskell - podělte se s námi v tomto vlákně! Pokud i velká s0cketka bude milostivá, třeba rozšíříme a vylepšíme její seznam.

Tady je jedna velice jednoduchá na rozehřátí:

powerset (potenční množinu) [a] -> [[a]] umí napsat každý. Zkuste si tedy rozmyslet co nejkratší „línou“ variantu, tedy takovou funkci

Kód: Vybrat vše

powerset :: [a] -> [[a]]

že bude fungovat i

Kód: Vybrat vše

(take 8) $ powerset [1..]

Ideální by bylo, aby pro 2^k vygenerovala všechny podmnožiny prvních k prvků.

[pj]

Napadá někoho něco podstatně jednoduššího než toto? (Když píšeš, mhb, že je ta úloha

velice jednoduchá

, tak prosím o kontrolu, protože mě moc jednoduchá nepřišla )

Kód: Vybrat vše

powerset :: [a] -> [[a]]
powerset list = [ y | y <- (diagonal [[]] list [[]])]

diagonal :: [[a]] -> [a] -> [[a]] -> [[a]]
diagonal xs [] ys = ys 
diagonal xs (l:ls) (y:ys) = y:(diagonal (xs ++ nxs) ls (ys ++ nxs))
	where nxs = (addNum xs l)

addNum :: [[a]] -> a -> [[a]]
addNum [] _ = []
addNum (x:xs) n = (n:x):(addNum xs n)

[radekm]

Kód: Vybrat vše

powerset xs = []:ps xs [[]]

ps [] _ = []
ps (x:xs) yet = let yet' = map (x:) yet
                in yet' ++ ps xs (yet ++ yet')

[radekm]

Nebo takto:

Kód: Vybrat vše

import List

powerset = ([]:) . concat . snd . mapAccumL f [[]]
  where
    f acc x = let new = map (x:) acc
              in (acc ++ new, new)

[radekm]

Ještě jednodušší:

Kód: Vybrat vše

powerset xs = ys
  where
    ys = [] : concat [map (x:) $ take (2^i) ys | (i, x) <- zip [0..] xs]

Komentář ke kódu:

• ys obsahuje podmnožiny
• (take (2^i) ys) je seznam se všemi podmnožinami seznamu (take i xs)
• (map (x:) $ bla bla) je stejné jako (map (x:) (bla bla)), dolar mi umožňuje vynechat závorku
• (map (x:) $ take (2^i) ys) přidá i-tý prvek (tedy x) k již hotovým podmnožinám
• concat zploští seznam tedy (concat [[[1]], [[2], [2, 1]], [[3],[3,1],[3,2],[3,2,1]]] == [[1],[2],[2,1],[3],[3,1],[3,2],[3,2,1]])

Komentář k principu:

1. Napřed ys obsahuje jen prázdnou podmnožinu.
2. Pro i-tý prvek seznamu xs (čísluji od nuly):
   • Seznam ys obsahuje právě všechny podmnožiny seznamu (take i xs)
   • My ale chceme, aby obsahoval právě podmnožiny seznamu (take (i+1) xs).
     Tedy do seznamu ys přidáme znovu všechny podmnožiny seznamu (take i xs) ale tentokrát
     ke každé z nich dáme i-tý prvek (to dělá ten map).