Haskell - zagnieżdżone pustych list

Question

Witam Haskellers i Haskellettes,

podczas czytania http://learnyouahaskell.com/ mój przyjaciel wpadł na pewien problem:

jest to możliwe w Haskell napisać rekurencyjną funkcję, która daje True jeśli wszystkie sub -sub -_- podlisty są puste. Moje pierwsze przypuszczenie było - powinno być - ale mam duży problem po prostu przy pisaniu adnotacji typu.

próbował coś podobnego

nullRec l = if null l 
       then True 
       else if [] `elem` l 
        then nullRec (head [l]) && nullRec (tail l) 
        else False 

jest - nie działa - :-)

wymyśliłem coś jak

• składanym z concat - aby uzyskać aa pojedynczą długą listę
  (daje mi problemy z implementacją)
• lub tworzenie nieskończonej, treelopodowej postaci danych - i czyni to z listy
  (jeszcze nie zaimplementowane)

ale ten brzmi trochę jak overkill dla tego problemu. co jest Twoje pomysły - na słoneczną niedzielę like this ;-)

Dzięki z góry

---

jako reakcja na wszystkich komentarzy - to jest zły styl bym chciał dodać to po prostu eksperyment !
NIE próbuj tego w domu! ;-)

Answer 1

Co powiesz na typografię?

{-# LANGUAGE FlexibleInstances, OverlappingInstances #-} 

class NullRec a where 
    nullRec :: a -> Bool 

instance NullRec a => NullRec [a] where 
    nullRec [] = True 
    nullRec ls = all nullRec ls 

instance NullRec a where 
    nullRec _ = False 

main = print . nullRec $ ([[[[()]]]] :: [[[[()]]]]) 

Answer 2

Nie jest to możliwe przy użyciu tylko polimorfizmu parametrycznego, z uwagi na następujące.

Rozważmy następujące wartości:

x = [8] :: [Int] 
y = [3.0] :: [Double] 
z = [[]] :: [[Int]] 

Oczywiście chcesz, aby funkcja działała zarówno x i y, zatem jego typ musi być null1 :: [a] -> Bool. (Czy ktoś może mi pomóc uczynić ten argument wyglądać formalny? W jaki sposób można pokazać, że jest to wyjątkowy najbardziej specyficzny kontekst mniej typ unifikowalny z [Int] -> Bool i [Double] -> Bool? Czy jest nazwa dla tej relacji między typami?)

teraz , jeśli masz ten typ, to null1 z będzie równe null1 x, ponieważ różnią się one tylko wartościami elementów listy, z których są pobierane. (nawet nie blisko formalnego dowodu znowu :()

Co chcesz za z jest null2 :: [[a]] -> Bool, które różnią się w zachowaniu, a tym samym dając null1 i null2 sama nazwa będzie wymagać przeciążenia.(patrz odpowiedź FUZxxl)