# Haskell - malé úložky 2.0

<{ForumPost(poster="mhb", timestamp=2009-04-30 22:45:26)}>
Ahoj,  
  
všichni určitě známe s0cketčiny „malé úložky“ - [http://s0cketka.blogspot.com/2006/01/ha ... lozky.html](http://s0cketka.blogspot.com/2006/01/haskell-male-ulozky.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 

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

 že bude fungovat i 

    (take 8) $ powerset [1..]

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

<{ForumPost(poster="pj", timestamp=2009-05-18 23:12:58)}>
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  :oops: )  

    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)
    


<{/ForumPost}>

<{ForumPost(poster="radekm", timestamp=2009-05-22 13:07:15)}>


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


<{/ForumPost}>

<{ForumPost(poster="radekm", timestamp=2009-05-22 13:32:49)}>
Nebo takto:  

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


<{/ForumPost}>

<{ForumPost(poster="radekm", timestamp=2010-01-08 09:29:54)}>
Ještě jednodušší:  

    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.
1.  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).

<{/ForumPost}>