string.clj

(defn charseq-in
  [& options]
  (let [{:keys [count min-count max-count chars]} options]
    (s/coll-of (or chars char?)
               :count count
               :min-count min-count
               :max-count max-count)))

(defn string-in
  [& options]
  (let [charseq-spec (apply charseq-in options)]
    (s/spec (s/and string?
                   #(s/valid? charseq-spec (vec (seq %))))
            :gen #(gen/fmap string/join (s/gen charseq-spec)))))

(s/def ::hostname-charseq
  (let [chars (set (seq (str "abcdefghijklmnopqrstuvwxyz"
                             "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                             "0123456789")))]
    (s/and
     (charseq-in :chars (conj chars \-) :min-count 1 :max-count 64)
     (s/cat :prefix (s/+ chars)
            :sections (s/* (s/cat :hyphen (s/+ #{\-})
                                  :suffix (s/+ chars)))))))

(s/def ::hostname
  (s/spec (s/and string?
                 #(s/valid? ::hostname-charseq (vec (seq %))))
          :gen #(gen/fmap string/join (s/gen ::hostname-charseq))))