Trong Haskell, concat xây dựng một danh sách uể oải nhưng phiên bản của riêng tôi với một twist, không

Question

Tôi đang cố gắng để thực hiện một chức năng tương đối đơn giản đó là gần như concat nhưng với một chút xoắn. Đó là nghĩa vụ phải nhị phân hoặc cùng nhau các yếu tố cuối cùng và đầu tiên của mỗi danh sách và kết hợp chúng trong quá trình này. Tôi đang nghiên cứu để viết mã có thể tận dụng khả năng của Stream Fusion trong Data.List.Stream

Tôi đã kiểm tra rằng concat trong cơ sở thực hiện những gì cần và xây dựng danh sách một cách lười biếng, tuy nhiên, phiên bản này tôi không được tạo. tại các cơ sở, concat được quy định như sau:

concat :: [[a]] -> [a] 
concat = foldr (++) [] 

(++) :: [a] -> [a] -> [a] 
(++) []  ys = ys 
(++) (x:xs) ys = x : xs ++ ys 

Dưới đây là mã của tôi:

bconcat :: [[Word8]] -> [Word8] 
bconcat = foldr1 bappend 

bappend :: [Word8] -> [Word8] -> [Word8] 
bappend as bs = init as ++ (last as .|. head bs) : tail bs 

Các câu hỏi tôi có được, làm thế nào để tôi viết những dòng này để danh sách được xây dựng một cách lười biếng? Tôi thậm chí đã cố gắng viết bappend bằng cách bắt chước định nghĩa (++) trong cơ sở nhưng nó không tạo ra sự khác biệt.

Hiện tại, tôi sử dụng mã sau đây, nó hoạt động theo cách tôi muốn nhưng hiệu suất tụt lại phía sau concat. Ngoài ra, nó sử dụng đệ quy rõ ràng mà tôi muốn tránh.

bconcat :: [[Word8]] -> [Word8] 
bconcat (a:b:xs) = init a ++ bconcat ((bappend (last a) b):xs) 
bconcat (a:[]) = a 
bconcat [] = [] 

bappend :: Word8 -> [Word8] -> [Word8] 
bappend !a bs = (a .|. head bs) : tail bs 

Vì vậy, câu hỏi tôi có là, làm thế nào để viết mã này để nó xây dựng danh sách một cách lười biếng và không có đệ quy rõ ràng?

Cảm ơn bạn đã dành thời gian.

Edit:

quan tâm chính của tôi, cho thời điểm này, là làm cho mã sạch, súc tích và understable với combinators chuẩn. Tôi vẫn còn rất nhiều người mới bắt đầu với tư duy chức năng và rất thích nhìn thấy một cách hiệu quả để đưa họ vào sử dụng ở đây.

Answer 1

Định nghĩa của bạn trông nghiêm khắc với tôi. Ví dụ: hãy thử đánh giá

length $ bconcat [[1,2,3],[4,undefined,6]] 

Nhưng bạn có thể xây dựng các khối cho. |. biểu hiện. Có lẽ bạn muốn ép buộc điều đó.

Bạn luôn có thể fuse thứ cho mình nếu họ không cầu chì cũng tự động:

bconcat [] = error "bconcat: empty outer list" 
bconcat (xs:xss) = loop xss xs 
    where loop [] ys = ys 
     loop ((x:xs):xss) [y] = let z = x .|. y in seq z $ z : loop xss xs 
     loop ([]:_) _ = error "bconcat: empty inner list" 
     loop xss (y:ys) = y : loop xss ys 

Answer 2

Bạn dường như có lỗi đánh máy, 'bapennd' phải là 'bappend' trong đoạn đầu tiên. Và tôi nghĩ rằng 'kết hợp' trong đoạn cuối nên là 'bconcat'.

Nó trông giống như lần đầu tiên (foldr1 bappend) sẽ khá lười biếng. Bạn có thể giải thích về sự thiếu lười biếng không?

Đối cần cả "init xs" và "xs cuối cùng" cùng một lúc, bạn có thể muốn có một traversal duy nhất của xs:

let un [] = error "no last element" 
    un (x:[]) = ([],x) 
    un (x:xs) = let (ys,z) = un xs 
       in (x:ys,z) 

này có một không gian và thời gian khác nhau trade-off. Nếu bạn luôn luôn buộc câu trả lời của bconcat theo thứ tự thì đó có thể là một sự cải tiến. "Các xs cuối cùng" giữ một tham chiếu đến phần đầu của toàn bộ danh sách và ngăn xs không bị thu gom rác cho đến khi nó bị ép buộc.

Answer 3

tôi có thể thay đổi câu trả lời bằng cách augustuss để phù hợp chặt chẽ hơn vấn đề ban đầu bằng cách viết:

bconcat2 [] = [] 
bconcat2 (xs:xss) = loop xss xs 
    where loop [] ys = ys 
     loop xss (y:[]) = gather xss y 
     loop xss (y:ys) = y : loop xss ys 
     loop (xs:xss) [] = loop xss xs 
     gather [] z = [z] 
     gather ([]:xss) z = gather xss z 
     gather ((x:[]):xss) z = gather xss $! z .|. x 
     gather ((x:xs):xss) z = let z' = z .|. x in z' : loop xss xs 

Ở trên bỏ qua bất kỳ danh sách nội bộ trống nào.