Bu uygulama neden Katlanabilir Tip Sınıfının kötü bir örneğidir?

Jan 02 2021

Harika Haskell Kitabı üzerinde çalışıyorum . Geçilebilir bölümün (21) sonunda, aşağıdaki Ağaç için bir örnek yazmam gerekiyor:

data Tree a =
    Empty
  | Leaf a
  | Node (Tree a) a (Tree a)

İşte çözümümün tam koduna bir bağlantı . Egzersizleri hem uygulamaya çalışıyor önerir foldMapve foldr. Bu şekilde uyguladım foldr(çağrı sırasına fazla düşünmeden):

foldr _ z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  f x $ foldr f (foldr f z left) right

Daha sonra foldMapaşağıdaki gibi uyguladım :

foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) = 
  foldMap f left <> f x <> foldMap f right

QuickCheck'in foldabletest grubunu çalıştırdığımda bazı hatalar alıyorum. Benim Değişen foldrtüm testler geçmesi aşağıdaki modellerine uygulanması:

foldr _ z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  foldr f (f x (foldr f z right)) left

Başarısız olan test durumunu kendi başıma çalıştırmayı denedim, ancak başarısızlığı yeniden oluşturamadım:

*Ch21_12_ExercisesTree Data.Monoid> tree = Node (Node (Leaf (-5)) 3 (Node (Leaf 3) 5 Empty)) (-2) Empty
*Ch21_12_ExercisesTree Data.Monoid> foldr (<>) (mempty :: Sum Int) t
Sum {getSum = 4}
*Ch21_12_ExercisesTree Data.Monoid> foldMap Sum t
Sum {getSum = 4}

foldQuickCheck'in kullandığı ing işlevi hakkında anlamadığım bir şey olduğundan şüpheleniyorum .

Sorular:

  1. Başarısızlıklar neden oluyor?
  2. QuickCheck tarafından testte kullanılan işlevi almanın bir yolu var mı?

Yanıtlar

4 duplode Jan 02 2021 at 06:30

foldrdeğerleri (monoid olarak) oluşturulabilen fonksiyonlara çeviren fonksiyon ile monoid foldMap kullanılarakEndo elde edilebilir. Öyleyse, eğer senin ...a -> b -> bab -> bfoldMap

foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) = 
  foldMap f left <> f x <> foldMap f right

... karşılık gelen şu foldrolmalıdır:

foldr f z Empty = id z  -- mempty amounts to id
foldr f z (Leaf x) = (f x) z
foldr f z (Node left x right) = 
  ((\e -> foldr f e left) . f x . (\e -> foldr f e right)) z  -- (<>) amounts to (.)

Biraz düzeltirsek ...

foldr f z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  foldr f (f x (foldr f z right)) left)

... foldrsorunuzda yazıldığı şekliyle doğru tanımını alıyoruz . Gerçekleştirmeler arasındaki farkın kompozisyon sırasına bağlı olması gerektiğinden, sizin de öğrendiğiniz gibi , değişmeyen bir monoidin denenmesi kolaylıkla başarısız bir duruma yol açar .

QuickCheck alt sorusunda, DDub'ın cevabını kabul ediyorum . .

3 DDub Jan 02 2021 at 05:40

Daha önce çıkardığınız gibi, başarısızlık almanızın nedeni, iki uygulamanın ayırt edilebilir olmasıdır, bu, değişmeli olmayan bir monoid kullanarak gözlemleyebilirsiniz.


Quickcheck tarafından kullanılan işlevi almak o kadar basit değil. Örneğin, biraz daha fazla bilgi için hızlı kontrol tarafından oluşturulan işlevlerle ilgili bu soruya / cevaba bakın Show.

Almanın yolu ShowQuickCheck dışına mümkün fonksiyonlarını işlevi sarılmasıdır türü . Bununla birlikte, aradığınız kod ( burada bulunur ) yalnızca işlevleri doğrudan kullanır, böylece bunlar asla gösterilemezler. Deneyebileceğiniz bir seçenek, işlevi yerine ve gerektiği gibi uygulayacağınız işlevin kendi sürümünüzü oluşturmaktır .FunfoldableFun a ba -> bapplyFun

2 javinor Jan 02 2021 at 03:00

Değişmeli bir Monoid kullandığımı yeni fark ettim ... Değişmeli olmayan bir Monoid kullanarak başarısızlığı yeniden yaratabildim:

> ftree = fmap (First . Just) tree
> foldr (<>) mempty ft
First {getFirst = Just (-2)}
> foldMap (First . Just) ft
First {getFirst = Just (First {getFirst = Just (-5)})}

Bu muhtemelen basit bir durumdur. Gerçek veri türlerine sahip üretim kodunda bunun çok daha karmaşık olabileceğini hayal ediyorum.